【LeetCode】43. 字符串相乘

1 问题

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

2 答案

这题直接不会

官方解，也用了int转换成整型，只不过是把单个字符转成int

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1=='0' or num2=='0':
            return '0'
        
        m, n = len(num1), len(num2)
        ansArr = [0] * (m+n)
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                ansArr[i+j+1] += int(num1[i])*int(num2[j])
        
        for i in range(m+n-1, 0, -1):  # 进位
            ansArr[i-1] += ansArr[i] // 10
            ansArr[i] %= 10

        index = 1 if ansArr[0] == 0 else 0
        ans = "".join(str(x) for x in ansArr[index:])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

$num1$ 和 $num2$ 的乘积的最大长度为 $m+n$，$num1[i]\times num2[j]$ 的结果位于 $ansArr[i+j+1]$