43. Multiply Strings 字符串相乘
刷题内容
- https://leetcode.com/problems/multiply-strings
- https://leetcode-cn.com/problems/multiply-strings
难度: Medium
参考了别人的思路：
- m位的数字乘以n位的数字的结果最大为m+n位：
- 99999 < 1000100 = 100000，最多为3+2 = 5位数。
- 先将字符串逆序便于从最低位开始计算。
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
lookup = {"0":0,"1":1,"2":2,"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,"9":9} # 节省查找时间，避免无休止使用ord函数来得到数字
if num1 == '0' or num2 == '0':
return '0'
num1, num2 = num1[::-1], num2[::-1]
tmp_res = [0 for i in range(len(num1)+len(num2))]
for i in range(len(num1)):
for j in range(len(num2)):
tmp_res[i+j] += lookup[num1[i]] * lookup[num2[j]]
res = [0 for i in range(len(num1)+len(num2))]
for i in range(len(num1)+len(num2)):
res[i] = tmp_res[i] % 10
if i < len(num1)+len(num2)-1:
tmp_res[i+1] += tmp_res[i]/10
return ''.join(str(i) for i in res[::-1]).lstrip('0') # 去掉最终结果头部可能存在的‘0’
觉得这样写才是最容易理解的，看一个具体的🌰:
input: num1, num2 = '91', '91'
tmp_res = [1,18,81,0]
res = [1,8,2,8]
最终返回 "8281"
要注意最终返回头部可能会有‘0’，所以我们用lstrip去除一下
