Leetcode 415 - Add Strings

Problem Statement

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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def addStrings(self, num1, num2):
s = 0
num1 = num1.zfill(len(num2))
num2 = num2.zfill(len(num1))
i = len(num1) - 1
place = 1
while i >= 0:
n1 = ord(num1[i]) - 48
n2 = ord(num2[i]) - 48
sum = (n1 + n2) * place
s += sum
place *= 10
i -= 1
return str(s)

Time: O(S) where S is the length of the longest string. The zfill operation is O(S) based on the length of the longest string and converting an int to str at the end is also O(N)

Space: O(1)

Explanation

zfill allows you to have strings of the same length which helps to simplify the problem when you have an input of "130" "12". You need to keep track of which place your at: 1s, 10s, 100s, etc so that is what the place variable is for. Keep looping until you get to the end of both strings and start from the end. Since you have to avoid using int(s), we can get the ordinal value of the character and subtract it from 48 since 48-57 are the numbers 0-9. Then you simply sum up the two numbers and multiply by the place and keep adding that up. Finally convert the result to a string. You could avoid the end conversion by building up a list and then calling ''.join(list) but it ends up being the same time complexity.