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为两字符串的长度
题外话
题外话
参考 有待研究
更多推荐
Leetcode 43 Multiply Strings
发布评论