415.md

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.

Thinking Process

1. Scan the two strings from tail towards the head, just like 1st grade math class
2. Terminate the loop until stirngs are depeleted and carry bit is 0

public String addStrings(String num1, String num2) {
    int carry = 0;
    StringBuilder sb = new StringBuilder();
    int l1 = num1.length() - 1;
    int l2 = num2.length() - 1;
    
    while(l1 >= 0 || l2 >= 0 || carry == 1){
        int a = (l1 >= 0) ? Character.getNumericValue(num1.charAt(l1--)) : 0;
        int b = (l2 >= 0) ? Character.getNumericValue(num2.charAt(l2--)) : 0;
        int sum = a + b + carry;
        if(sum < 10){
            sb.append(sum);
            carry = 0;
        }else{
            sb.append(sum - 10);
            carry = 1;
        }
    }

    return sb.reverse().toString();
}

Complexity

1. Array is scanned once, time complexity is O(n)
2. The result is stored in a new string, hence space complexity is O(n)