[LeetCode] 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.

Thought process:

Iterate the strings from right to left. Add the characters until both strings are iterated. If one of the pointer is out of bound, use 0 for that string. Use a variable to keep track of carry.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Solution { public String addStrings(String num1, String num2) { StringBuilder sum = new StringBuilder(); int length1 = num1.length(); int length2 = num2.length(); int i = 1; int carry = 0; while (i <= length1 || i <= length2) { int digit1 = i <= length1 ? num1.charAt(length1 - i) - '0' : 0; int digit2 = i <= length2 ? num2.charAt(length2 - i) - '0' : 0; int digitSum = digit1 + digit2 + carry; carry = digitSum / 10; sum.append(digitSum % 10); i++; } if (carry > 0) { sum.append(carry); } return sum.reverse().toString(); } }

Time complexity:
Say the length of num1 is a and length of num2 is b. The overall time complexity is O(a + b).