Leetcode 415  Add Strings
Problem Statement
Given two nonnegative 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 09.
Both num1 and num2 does not contain any leading zero.
You must not use any builtin BigInteger library or convert the inputs to integer directly.
Solution


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 4857 are the numbers 09. 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.