【LeetCode每天一题】Multiply Strings(字符串乘法)

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"                    Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"             Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly

思路

　　这道题和之前做的字符串加法挺相似的，唯一有区别的是，加法和乘法的计算规则不一样。加法是对应位置相加，只要一次遍历。而乘法则是需要两层循环，因为num1中的每一位都需要乘以num2，最后相加得到结果。这就意味着在一定程度上乘法的细节处理更加繁琐一些。但是只要抓住核心部分最终都能写出来。时间复杂度为O(n*m)(n,m分别为num1和num2的长度)，空间复杂度为O(m+n)。

实现代码

 1 class Solution(object):
 2     def multiply(self, num1, num2):
 3         """
 4         :type num1: str
 5         :type num2: str
 6         :rtype: str
 7         """
 8         res_list = [0] * (len(num1) + len(num2))   # 存储最终结果的数组
 9         start = len(res_list)-1                    # 每一次循环相加位置的下标
10 
11         for n1 in reversed(num1):                  #  两层循环，意思是使用num2中每一位乘以num1中的每一位
12             tempPos = start                        # 当前循环内的下标，意思是num1个位乘以num2的每一位时，第一位存储的是个位。
13             for n2 in reversed(num2):         
14                 res_list[tempPos] += int(n1) * int(n2)        # 存储当前结果
15                 res_list[tempPos-1] += res_list[tempPos]/10   #存储低一位溢出的数
16                 res_list[tempPos] %= 10                       # 存储个位的数
17                 tempPos -= 1                                  # 进一位，意思是下一次结果存储的位置
18             start -= 1                                # 
19 
20         i = 0
21         while i < len(res_list)-1 and res_list[i] == 0:  # 去除前面的0， 并且防止最终结果为零的输出。
22             i += 1
23 
24         return ''.join(map(str, res_list[i:]))          # 返回字符串