1.9 Add Strings

Description

Given two non-negative numbers 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.

Method

add from tail to head, use a pointer to count carry

Time and Space Complexity

o(n + m)

Code

public class Solution {

  public String addStrings(String num1, String num2) {
       if (num1 == null || num1.length() == 0){
           return num2;
       }
       if (num2 == null || num2.length() == 0){
           return num1;
       }
       int add = 0;
       int i = num1.length() - 1;
       int j = num2.length() - 1;
       StringBuilder sb = new StringBuilder();
       while (i >= 0 && j >= 0){
             int sum = (num1.charAt(i) - '0') + (num2.charAt(j) -'0') + add;
             int digit = sum % 10;
             add = sum / 10;
             sb.insert(0,digit);
             i--;
             j--;
       }
       while (i >= 0){
             int digit = (num1.charAt(i) - '0' + add) % 10;
             add = (num1.charAt(i) - '0' + add) / 10;
             sb.insert(0,digit);
             i--;
       }
       while (j >= 0){
             int digit = (num2.charAt(j) - '0' + add) % 10;
             add = (num2.charAt(j) - '0' + add) / 10;
             sb.insert(0,digit);
             j--;
       }
       if (add == 1) {
           sb.insert(0, add);
       }
       return sb.toString();

}

}