43. 字符串相乘
43. 字符串相乘
题目
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
andnum2
consist of digits only.- Both
num1
andnum2
do not contain any leading zero, except the number0
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 | 价格减免 | 字符串 |