43. 字符串相乘

🟠   🔖  数学 字符串 模拟  🔗 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.

题目大意

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

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

解题思路

需要逐步模拟乘法过程，确保处理大数字时不会溢出。

• 创建一个大小为 m + n 的数组 res，其中 m 和 n 分别是两个输入字符串的长度。这个大小足够存储乘法结果的最大可能位数。
• 从两个字符串的末尾开始反向遍历（从最低位到最高位）。对于每一对数字，将它们转换为整数进行相乘，并将结果放置在 res 数组的相应位置。
• 在将结果放入 res 数组时，需跟踪进位。由于乘积可能超过 10，因此需要计算进位并相应地调整 res 数组中的当前位。
• 填充完 res 数组后，将其转换为字符串。在此过程中，跳过前导零，构建最终的乘积字符串。
• 处理边界情况，若字符串为空，乘积应直接返回 "0"。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别是两个字符串的长度，因为需要遍历每一个数字。
• 空间复杂度：O(m + n)，用于存储中间结果的 res 数组。

代码

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
	const m = num1.length,
		n = num2.length;
	let res = new Array(m + n).fill(0);

	// 模拟乘法过程
	for (let i = m - 1; i >= 0; i--) {
		for (let j = n - 1; j >= 0; j--) {
			const product = (num1[i] - '0') * (num2[j] - '0');
			const sum = product + res[i + j + 1];

			res[i + j + 1] = sum % 10;
			res[i + j] += (sum / 10) | 0;
		}
	}

	// 跳过前导零
	let i = 0;
	while (i < res.length && res[i] == 0) {
		i++;
	}
	const str = res.join('').slice(i);

	// 处理边界条件
	return str.length == 0 ? '0' : str;
};

相关题目

题号	标题	题解	标签	难度
2	两数相加	[✓]	递归 链表 数学
66	加一	[✓]	数组 数学
67	二进制求和	[✓]	位运算 数学 字符串 1+
415	字符串相加	[✓]	数学 字符串 模拟
2288	价格减免		字符串