LeetCode-43 字符串相乘

1. 题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

• num1 和 num2 的长度小于110。
• num1 和 num2 只包含数字 0-9。
• num1 和 num2 均不以零开头，除非是数字 0 本身。
  不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

2. 我的AC

方法一

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        return str(int(num1) * int(num2))

方法二：大整数乘法

• m 位乘 n 位结果最大为 m+n 位
• 建立中间数组，第 i 位乘第 j 位的结果保存在第 i+j 位
• 处理中间数组，个位数和进位
• 删除高位的0

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1 = num1[::-1]
        num2 = num2[::-1]
        length1 = len(num1)
        length2 = len(num2)
        temp = [0] * (length1 + length2)
        for i in range(length1):
            for j in range(length2):  
                temp[i+j] += int(num1[i]) * int(num2[j])
    
        result = []
        for i, num in enumerate(temp):
            digit = num % 10
            carry = num / 10 
            result.insert(0, str(digit))
            if i < length1 + length2 - 1:
                temp[i+1] += carry
        while result[0] == '0' and len(result) > 1: # "9133" * "0"
            result.pop(0)   
        return "".join(result)

3. 小结

1. 删除列表第0位

result.pop(0)