Description
Given two non-negative integers num1
and num2
represented as string, return the sum of num1
and num2
.
Note:
- The length of both
num1
andnum2
is < 5100. - Both
num1
andnum2
contains only digits0-9
. - Both
num1
andnum2
does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solutions
实现字符串的加法。
1. Direct
# Time: O(n)
# Space: O(n)
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
if not num1 or not num2:
return num2 or num1
str_int = dict(zip(list('0123456789')+['10', '11', '12', '13', '14', '15', '16', '17', '18'], range(19)))
int_str = dict(zip(range(19), list('0123456789')+['10', '11', '12', '13', '14', '15', '16', '17', '18']))
n1, n2 = len(num1), len(num2)
res = ['0'] * (max(n1, n2) + 1)
n = len(res)
for i in range(n):
add = str_int[res[n - i - 1]] \
+ (str_int[num1[n1 - i - 1]] if n1 - i - 1 >= 0 else 0) \
+ (str_int[num2[n2 - i - 1]] if n2 - i - 1 >= 0 else 0)
res[n - i - 1] = int_str[add % 10]
res[n - i - 2] = int_str[str_int[res[n - i - 2]] + add // 10]
for i in range(n):
if res[i] != '0' or i == n-1:
return ''.join(res[i:])
return ''
# 315/315 cases passed (104 ms)
# Your runtime beats 12.07 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)