LeetCode 415. 字符串相加

◎

本节目标

从两个十进制字符串的末位开始相加，并将进位持续传播到更高位。

这道题使用解析与大整数中的逐位算术模板：从低位到高位读取，并把每一位产生的进位传给下一位。

查看原题

题意与约束

给定两个非负十进制整数字符串，不能把它们整体转换为内置数值类型，返回它们的和。

从末位开始相加

两个指针分别从字符串末尾向前移动。每轮把两个可用数字和 carry 相加，个位追加到结果，十位成为下一轮进位。循环条件还必须包含 carry，这样 999 + 1 的最高位才不会遗漏。

结果方向

低位先被计算出来，因此先把个位依次追加到结果字符串，再在全部处理完成后反转。两个输入长度不同的一侧，在对应指针越界后按零处理。

代码实现

C++

C++17

#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string addStrings(string num1, string num2) {
        int firstIndex = static_cast<int>(num1.size()) - 1;
        int secondIndex = static_cast<int>(num2.size()) - 1;
        int carry = 0;
        string result;

        while (firstIndex >= 0 || secondIndex >= 0 || carry > 0) {
            int digit = carry;
            if (firstIndex >= 0) {
                digit += num1[firstIndex] - '0';
                firstIndex--;
            }
            if (secondIndex >= 0) {
                digit += num2[secondIndex] - '0';
                secondIndex--;
            }
            result.push_back(static_cast<char>('0' + digit % 10));
            carry = digit / 10;
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

Python

Python 3

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        first_index = len(num1) - 1
        second_index = len(num2) - 1
        carry = 0
        digits: list[str] = []

        while first_index >= 0 or second_index >= 0 or carry:
            digit = carry
            if first_index >= 0:
                digit += int(num1[first_index])
                first_index -= 1
            if second_index >= 0:
                digit += int(num2[second_index])
                second_index -= 1
            digits.append(str(digit % 10))
            carry = digit // 10

        return ''.join(reversed(digits))

复杂度分析

设两个字符串长度为 m 和 n，时间复杂度为 O(max(m, n))，额外空间复杂度为 O(max(m, n))。

易错点

• while 条件漏掉进位，连续进位后少写最高位。
• 直接把字符相加，忘记减去字符 '0'。
• 处理不等长字符串时访问已经越界的一侧。

模式迁移

字符串减法、十进制比较和逐位除法同样从低位或高位维护局部状态；只要数值范围不可靠，就把每一位当作独立信息处理。