415 Add Strings

415. Add Strings

1. Question

Given two non-negative integersnum1andnum2represented as string, return the sum ofnum1andnum2.

Note:

1. The length of bothnum1andnum2is < 5100.

2. Bothnum1andnum2contains only digits0-9.

3. Bothnum1andnum2does not contain any leading zero.

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

2. Implementation

class Solution {
    public String addStrings(String num1, String num2) {
        if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
            return "";
        }

        StringBuilder res = new StringBuilder();

        int index1 = num1.length() - 1;
        int index2 = num2.length() - 1;
        int sum = 0;

        while (index1 >= 0 || index2 >= 0) {
            int digit1 = index1 >= 0 ? num1.charAt(index1) - '0' : 0;
            int digit2 = index2 >= 0 ? num2.charAt(index2) - '0' : 0;
            sum += digit1 + digit2;
            res.append(sum % 10);
            sum /= 10;
            --index1;
            --index2;
        }

        if (sum != 0) {
            res.append(sum);
        }
        return res.reverse().toString();
    }
}

3. Time & Space Complexity

时间复杂度O(Max(m,n)), m是num1的长度, n是num2的长度, 空间复杂度O(Max(m, n))