LeetCode 043 Multiply Strings

LeetCode

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = “2”, num2 = “3”
Output: “6”

Example 2:

Input: num1 = “123”, num2 = “456”
Output: “56088”

Constraints:

1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only.
* Both num1 and num2 do not contain any leading zero, except the number 0 itself.

题目大意：

求字符串乘法结果

解题思路：

模拟小学乘法

解题步骤：

N/A

注意事项：

1. 模拟小学乘法，开一个大小为len(num1) + len(num2)的整数数组，内外循环计算每位结果。这位可能是大于20的数，如20, 30..。计算前先反转输入，得到最后结果后也反转。
2. 结果要消除前缀0，但注意0乘以0的情况会返回空，所以要特别处理。

Python代码：

def multiply(self, num1: str, num2: str) -> str:
	digits = [0] * (len(num1) + len(num2))
	num1, num2 = num1[::-1], num2[::-1]
	for i in range(len(num1)):
		for j in range(len(num2)):
			digits[i + j] += int(num1[i]) * int(num2[j])
	carry, res = 0, ''
	for i in range(len(digits)):
		n = digits[i] + carry
		carry = n // 10
		res += str(n % 10)
	return '0' if res[::-1].lstrip('0') == '' else res[::-1].lstrip('0')

算法分析：

时间复杂度为O(n)，空间复杂度O(1)