415. 字符串相加

Problem: 415. 字符串相加

思路

字符串模拟大数加法。
加法是从个位数开始计算，需要倒序。

具体步骤为：

1. 利用数组存储倒序的结果
2. 倒序遍历每个数字，相加，计算余数（当前位的元素）和进位
3. 将数组倒序拼接成字符串即可。

需要注意，Python，list的join方法只能将元素是字符的列表拼接成字符串。
如果需要删除前导0，则需要删除列表后面的0（最多保留一个，模拟结果相加为0的情况）

while len(res) > 1 and res[-1] == '0':
    res.pop()

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

Code

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        n1 = len(num1) - 1
        n2 = len(num2) - 1

        res = [] # 存储结果
        carry = 0 # 进位
        while carry or n1 >= 0 or n2 >= 0:
            a = int(num1[n1]) if n1 >=0 else 0
            b = int(num2[n2]) if n2 >= 0 else 0

            n1 -= 1
            n2 -= 1

            res.append(f'{(a + b + carry) % 10}')
        
            carry = (a + b + carry) // 10
        while len(res) > 1 and res[-1] == '0':
            res.pop()
            
        return "".join(res[::-1])