leetcode43. 字符串相乘

字符串相乘

'''
今天分享的题目非常有意思：大数(字符串存储)相乘str1*str2
m位数字*n位数字最多只有m+n位
reverse_str1=str1[::-1]
reverse_str2=str2[::-1]

tmp_res[i+j]=reverse_str1[i]*reverse_str1[j]

res[i] = tmp_res[i] % 10
tmp_res[i+1] += tmp_res[i]/10

-----------------------------------------------

input: num1, num2 = '91', '91'
tmp_res = [1,18,81,0]
res = [1,8,2,8]

'''
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} # 节省查找时间
        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+1] += tmp_res[i]//10 
        return ''.join(str(i) for i in res[::-1]).lstrip('0')  # 去掉最终结果头部可能存在的‘0’