【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:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9 .
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. 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)。

实现代码

 class Solution(object):

     def multiply(self, num1, num2):

         """

         :type num1: str

         :type num2: str

         :rtype: str

         """

         res_list = [0] * (len(num1) + len(num2))   # 存储最终结果的数组

         start = len(res_list)-1                    # 每一次循环相加位置的下标

         for n1 in reversed(num1):                  #  两层循环，意思是使用num2中每一位乘以num1中的每一位

             tempPos = start                        # 当前循环内的下标，意思是num1个位乘以num2的每一位时，第一位存储的是个位。

             for n2 in reversed(num2):

                 res_list[tempPos] += int(n1) * int(n2)        # 存储当前结果

                 res_list[tempPos-1] += res_list[tempPos]/10   #存储低一位溢出的数

                 res_list[tempPos] %= 10                       # 存储个位的数

                 tempPos -= 1                                  # 进一位，意思是下一次结果存储的位置

             start -= 1                                # 

         i = 0

         while i < len(res_list)-1 and res_list[i] == 0:  # 去除前面的0， 并且防止最终结果为零的输出。

             i += 1

         return ''.join(map(str, res_list[i:]))          # 返回字符串