Given two non-negative integers 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.
C Solution:
char* addStrings(char* num1, char* num2) {
int len1 = strlen(num1), len2 = strlen(num2);
int len = len1 > len2 ? len1 : len2;
char *res = malloc(len + 2);
res[len + 1] = 0;
int i, carry = 0;
for (i = 0; carry || i < len1 || i < len2; i++) {
carry += i < len1 ? num1[len1 - 1 - i] - '0' : 0;
carry += i < len2 ? num2[len2 - 1 - i] - '0' : 0;
res[len - i] = carry % 10 + '0';
carry /= 10;
}
if (i - 1 == len) return res;
for (i = 1; i < len + 2; i++) res[i - 1] = res[i];
return res;
}
Python Solution:
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
if not num1: return num2[:]
if not num2: return num1[:]
i = len(num1) - 1
j = len(num2) - 1
carry = 0
res = []
while i > -1 or j > -1 or carry:
if i > -1:
carry += ord(num1[i]) - ord('0')
i -= 1
if j > -1:
carry += ord(num2[j]) - ord('0')
j -= 1
res.append(str(carry % 10))
carry //= 10
return "".join(res[::-1])
Summary:
- Don't return res + 1, that's evil.
- 3ms, 15%
- almost same as 67. Add Binary
LeetCode: 415. Add Strings
近期评论