FXTi's blog
0%

add-strings

Posted on Edited on

Add Strings – LeetCode 415

Problem

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 and num2 is < 5100.

Both num1 and num2 contains only digits 0-9.

Both num1 and num2 does not contain any leading zero.

You must not use any built-in BigInteger library or convert the inputs to integer directly.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string addStrings(string num1, string num2) {
        string res = "";
        int m = num1.size(), n = num2.size(), i = m - 1, j = n - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int a = i >= 0 ? num1[i--] - '0' : 0;
            int b = j >= 0 ? num2[j--] - '0' : 0;
            int sum = a + b + carry;
            res.insert(res.begin(), sum % 10 + '0');
            carry = sum / 10;
        }
        return carry ? "1" + res : res;
    }
};

思路

简单的看题说话。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$10$ ms，排名$50.61\%$

Better

思路

还没看到更好的思路。