Google
415 Add Strings

415. Add Strings

1. Question

Given two non-negative integersnum1andnum2represented as string, return the sum ofnum1andnum2.
Note:
  1. 1.
    The length of bothnum1andnum2is < 5100.
  2. 2.
    Bothnum1andnum2contains only digits0-9.
  3. 3.
    Bothnum1andnum2does not contain any leading zero.
  4. 4.
    You must not use any built-in BigInteger library or convert the inputs to integer directly.

2. Implementation

1
class Solution {
2
public String addStrings(String num1, String num2) {
3
if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) {
4
return "";
5
}
6
7
StringBuilder res = new StringBuilder();
8
9
int index1 = num1.length() - 1;
10
int index2 = num2.length() - 1;
11
int sum = 0;
12
13
while (index1 >= 0 || index2 >= 0) {
14
int digit1 = index1 >= 0 ? num1.charAt(index1) - '0' : 0;
15
int digit2 = index2 >= 0 ? num2.charAt(index2) - '0' : 0;
16
sum += digit1 + digit2;
17
res.append(sum % 10);
18
sum /= 10;
19
--index1;
20
--index2;
21
}
22
23
if (sum != 0) {
24
res.append(sum);
25
}
26
return res.reverse().toString();
27
}
28
}
Copied!

3. Time & Space Complexity

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