Description
https://leetcode.com/problems/add-strings/
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
Example 1:
Input: num1 = "11", num2 = "123" Output: "134"
Example 2:
Input: num1 = "456", num2 = "77" Output: "533"
Example 3:
Input: num1 = "0", num2 = "0" Output: "0"
Constraints:
1 <= num1.length, num2.length <= 104num1andnum2consist of only digits.num1andnum2don’t have any leading zeros except for the zero itself.
Follow up: Could you solve it without using any built-in BigInteger library or converting the inputs to integer directly?
Explanation
Sum the two num strings by digits.
Python Solution
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
num1s = []
for c in num1:
num1s.insert(0, int(c))
num2s = []
for c in num2:
num2s.insert(0, int(c))
i = 0
j = 0
carry = 0
results = []
while i < len(num1s) and j < len(num2s):
digit = (num1s[i] + num2s[j] + carry) % 10
carry = (num1s[i] + num2s[j] + carry) // 10
results.insert(0, str(digit))
i += 1
j += 1
while i < len(num1s):
digit = (num1s[i] + carry) % 10
carry = (num1s[i] + carry) // 10
results.insert(0, str(digit))
i += 1
while j < len(num2s):
digit = (num2s[j] + carry) % 10
carry = (num2s[j] + carry) // 10
results.insert(0, str(digit))
j += 1
if carry > 0:
results.insert(0, str(carry))
return "".join(results)
- Time Complexity: O(N).
- Space Complexity: O(N).