O(max(m, n)) O(max(m, n))
Intuition
Add from the least significant digit, carrying overflow to the next column — exactly how you add by hand.
Explanation
Grade-school addition
Walk both strings from the right. At each step add the two digits plus the carry; the ones digit is appended and the tens become the carry. Continue until both strings and the carry are exhausted, then reverse.
while i>=0 or j>=0 or carry:
s = digit(num1) + digit(num2) + carry
append s % 10; carry = s // 10
Worked example
"456" + "77": 6+7=13 (3, carry 1), 5+7+1=13 (3, carry 1), 4+0+1=5 → "533".
Complexity
- Time: O(max(m, n)).
- Space: O(max(m, n)).
Implementation
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || carry > 0) {
int a = i >= 0 ? num1.charAt(i) - '0' : 0;
int b = j >= 0 ? num2.charAt(j) - '0' : 0;
int s = a + b + carry;
sb.append(s % 10);
carry = s / 10;
i--;
j--;
}
return sb.reverse().toString();
}
}