0. 链接

1. 题目

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.

2. 思路1：从低位到高位逐个计算乘法, 然后汇总结果

2.1 初始化结果数组array

2.2 对num2从低位到高位遍历每个数字num2[num2_len - 1 - i]
对于每个num2[num2_len - 1 - i], 对num1从低位到高位遍历每个数字num2[num2_len - 1 - j], 计算两数乘积, 放到array[i + j]上

2.3 对array进行遍历，逐渐计算进位

2.4 倒序遍历array, 找到首个不为0的值作为开始, 将结果数组连接为字符串返回

3. 代码

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        num1_len = len(num1)
        num2_len = len(num2)

        num1 = [ord(x) - ord('0') for x in num1]
        num2 = [ord(x) - ord('0') for x in num2]

        array = list()
        for i in range(num2_len):
            each_num2 = num2[num2_len - 1 - i]
            for j in range(num1_len):
                each_num1 = num1[num1_len - 1 - j]
                idx = i + j
                multi_result = each_num2 * each_num1
                if idx > len(array) - 1:
                    array.append(multi_result)
                else:
                    array[idx] += multi_result

        array_len = len(array)
        for i in range(array_len):
            if array[i] >= 10:
                step_up = array[i] // 10
                if i == array_len - 1:
                    array.append(step_up)
                else:
                    array[i + 1] += step_up
                array[i] = array[i] % 10

        rtn = '0'
        started = False
        for i in range(len(array) - 1, -1, -1):
            if started is False and array[i] > 0:
                started = True
                rtn = ''

            if started:
                rtn += str(array[i])

        return rtn
        
        
solution = Solution()
print(solution.multiply('2', '3'))
print(solution.multiply('123', '456'))
print(solution.multiply('9999', '0'))

输出结果

6
56088
0

4. 结果

image.png

5. 方法二: 分别解析两个字符串所代表的数值，然后将两个数值相乘

6. 代码

class Solution1:
    def multiply(self, num1: str, num2: str) -> str:
        number1 = 0
        number2 = 0
        for char1,char2 in zip_longest(num1,num2):
            if char1 is not None:
                number1 = 10 * number1 + (ord(char1) - ord('0'))
            if char2 is not None:
                number2 = 10 * number2 + (ord(char2) - ord('0'))
        return str(number1 * number2)


solution = Solution1()
print(solution.multiply('2', '3'))
print(solution.multiply('123', '456'))
print(solution.multiply('9999', '0'))

输出结果