415. Add Strings

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.

從個位數開始相加，一開始先倒著加到res裡，因為如果每次都insert新的數字到res string的begin()，這樣時間複雜度會比較差，所以每次先appen到res string的尾巴，最後再reverse一次。

string addStrings(string num1, string num2) { // time: O(max(m, n)); space: O(max(m, n))
    string res;
    int m = num1.length(), n = num2.length();
    int i = m - 1, j = n - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int n1 = i >= 0 ? num1[i--] - '0' : 0;
        int n2 = j >= 0 ? num2[j--] - '0' : 0;
        int sum = n1 + n2 + carry;
        res += (char)(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}