Leetcode 43 Multiply Strings

Leetcode 43 Multiply Strings"/>

Leetcode 43 Multiply Strings

Leetcode 43 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.

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

• 思路一，题目中显式要求了不能直接将字符串转为数字直接相乘（如果这样做，这道题完全没有意义）。那么如何解决两数相乘问题，首先想到的自然是 小学生都会的竖式乘法。

  ​ 10 * 10 =

  ​ 0 0 +

  ​ 1 0 0 = （加最后一个0，只是为了便于理解

  ​ 100

  按照这样的思路，可以得到如下代码：

class Solution:def multiply(self, num1: str, num2: str) -> str:result = 0part_result = 0length1 = len(num1)length2 = len(num2)if length2 > length1:num1, num2 = num2, num1length1, length2 = length2, length1for i in range(length2 - 1, -1, -1):part_result = 0for j in range(length1 - 1, -1, -1):x = int(num2[i]) * int(num1[j])part_result += x * (10 ** (length1 - j - 1))result += part_result * (10 ** (length2 - i - 1))return str(result)

时间复杂度为 O ( M ∗ N ) ， M 、 N 为 两 字 符 串 的 长 度 O(M*N)，M、N为两字符串的长度 O(M∗N)，M、N为两字符串的长度

题外话

题外话

参考 有待研究