Description

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. 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)

References

  1. 415. Add Strings