This algorithm adds two numbers digit by digit using their string representations.
I am wondering what the time and space complexities of the following algorithm are. In particular, I am wondering about the string addition lines, which may make it a quadratic time complexity. In general, what are some ways to improve the performance here?
def addStrings(self, num1: str, num2: str) -> str:
n1 = len(num1) - 1
n2 = len(num2) - 1
carry = 0
ans = ''
while n1 >= 0 or n2 >= 0 or carry > 0:
n1_digit = int(num1[n1]) if n1 >= 0 else 0
n2_digit = int(num2[n2]) if n2 >= 0 else 0
number = n1_digit + n2_digit + carry
if number >= 10:
ans = str(number % 10) + ans
carry = 1
else:
ans = str(number) + ans
carry = 0
n1 -= 1
n2 -= 1
return ans