LeetCode 43. [Python] Multiply Strings
原题链接
中等
作者:
徐辰潇
,
2021-01-27 08:31:59
,
所有人可见
,
阅读 451
class Solution:
def multiply(self, num1: str, num2: str) -> str:
#TC: O(n1*n2)
#SC: O(n1*n2)
n1 = len(num1)
n2 = len(num2)
res = [0]*(n1+n2) #For example, 999*999, the number of digits is less than 1000*1000, 7-1 = 6
for i in range(n1):
carry = 0
for j in range(n2):
a1 = ord(num1[-1-i]) - ord('0')
a2 = ord(num2[-1-j]) - ord('0')
product = a1*a2 + carry + res[i+j] #zero based merit
res[i+j] = product % 10
carry = product // 10
res[i+n2] += carry
for ele in reversed(res):
if ele == 0:
res.pop()
else:
break
if len(res) == 0:
return '0'
return "".join(list(map(str, res[::-1])))