跳至主要內容

43. 字符串相乘


43. 字符串相乘open in new window

🟠   🔖  数学 字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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.

题目大意

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

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

解题思路

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

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

复杂度分析

  • 时间复杂度O(m * n),其中 mn 分别是两个字符串的长度,因为需要遍历每一个数字。
  • 空间复杂度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两数相加open in new window[✓]递归 链表 数学
66加一open in new window[✓]数组 数学
67二进制求和open in new window[✓]位运算 数学 字符串 1+
415字符串相加open in new window[✓]数学 字符串 模拟
2288价格减免open in new window字符串