LC 0415 [E] Add Strings - ALawliet/algorithms GitHub Wiki
- use
ord('digit') - ord('0')
to convert str to int - use 2 pointers or pop off a stack to add from the ends while nums1 or nums2
- start with 0 and compute (top + bot + carry) value (% 10) before carry (// 10)
- add leftover carry at the end if any for last digit
- reverse result at end [::-1] or deque.appendleft() to get correct order
T: O(max(n1+n2))
S: O(max(n1+n2))
why - ord('0')
?
>>> ( ord('9') + ord('5') )
110
>>> ord('0')
48
>>> ( ord('9')-ord('0') + ord('5')-ord('0') )
14
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = deque()
t = list(num1)
b = list(num2)
carry = 0
while t or b:
top = bot = 0
if t:
top = ord(t.pop()) - ord('0')
if b:
bot = ord(b.pop()) - ord('0')
carry, drop = divmod(top + bot + carry, 10)
# drop = (top + bot + carry) % 10 # must come first
# carry = (top + bot + carry) // 10
res.appendleft(str(drop))
if carry:
res.appendleft(str(carry))
return ''.join(res)
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = deque()
carry = 0
t = len(num1)-1
b = len(num2)-1
while t >= 0 or b >= 0:
top = bot = 0
if t >= 0:
top = ord(num1[t]) - ord('0')
t -= 1
if b >= 0:
bot = ord(num2[b]) - ord('0')
b -= 1
carry, drop = divmod(top + bot + carry, 10)
res.appendleft(drop)
if carry: res.appendleft(carry)
return ''.join([str(d) for d in res])