LeetCode 43. 字符串相乘
题目描述
题意分析
两个非负整数分别用十进制字符串
num1、num2表示，要求返回它们的乘积字符串。不能把整个输入转换成整数，也不能借助大整数库；把单个数字字符转换成0到9后计算是允许的。两个字符串都不含多余的前导零，零只会表示为
"0"。结果也应使用正常的十进制表示：非零结果不保留前导零，零返回"0"。输入最多各有 200 位，因此需要直接在数位上完成乘法。
解法：数组模拟竖式乘法
核心思路
[!blue]
竖式乘法把两个数拆成数位：每一对数字相乘，再按它们的位权累加。设两串长度为 $m$、$n$，两数分别小于 $10^m$ 和 $10^n$，乘积一定小于 $10^{m+n}$，所以用长度为
m + n的数组digits就能容纳结果；数组右端保存个位。
num1[i]距离个位有m - 1 - i位，num2[j]距离个位有n - 1 - j位。两者相乘后，乘积的本位距离个位有m + n - 2 - i - j位，换成结果数组从左到右的下标就是pos = i + j + 1。因此，本位写到digits[pos]，进位写到它左边的digits[pos - 1]。同一个结果位置会收到多对数字的贡献，不能直接写入本次乘积。应先计算
sum = digits[pos] + x * y，把sum % 10留在本位，再把sum / 10累加到高一位。这个拆分只改变存储形式，不改变数组表示的总数值。两层循环都从右向左进行。高位暂时累加到大于
9也没关系：之后轮到该位置作为本位计算时，会把旧值一起拆成数字和进位。这样的顺序保证每个位置最后一次作为本位处理时，来自右侧的进位已经到齐；最左侧只接收最终进位，而乘积最多m + n位，不会再溢出数组。所有数位对处理完后，数组就表示完整乘积。任一输入为
"0"时提前返回；其余情况跳过数组前导零，把剩余数字依次拼成字符串。
解题步骤
- 任一输入为
"0"时直接返回"0"，否则创建长度为m + n的零数组digits。- 从两串末尾向前枚举下标
i、j，把当前字符转换为数字x、y。- 令
pos = i + j + 1，计算sum = digits[pos] + x * y。- 更新
digits[pos] = sum % 10，并执行digits[pos - 1] += sum / 10。- 完成所有乘积累加后，找到第一个非零位置，将其及后面的数字拼接并返回。
代码实现
class Solution {
public String multiply(String num1, String num2) {
if ("0".equals(num1) || "0".equals(num2)) {
return "0";
}
int m = num1.length();
int n = num2.length();
int[] digits = new int[m + n];
for (int i = m - 1; i >= 0; i--) {
int x = num1.charAt(i) - '0';
for (int j = n - 1; j >= 0; j--) {
int y = num2.charAt(j) - '0';
int pos = i + j + 1;
// 这个位置可能已有其他数位贡献，先合并旧值再处理进位。
int sum = digits[pos] + x * y;
digits[pos] = sum % 10;
// 高位贡献要累加，不能覆盖此前的进位。
digits[pos - 1] += sum / 10;
}
}
StringBuilder ans = new StringBuilder();
int idx = 0;
while (idx < digits.length && digits[idx] == 0) {
idx++;
}
while (idx < digits.length) {
ans.append(digits[idx]);
idx++;
}
return ans.toString();
}
}
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m := len(num1)
n := len(num2)
digits := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
x := int(num1[i] - '0')
for j := n - 1; j >= 0; j-- {
y := int(num2[j] - '0')
pos := i + j + 1
// 这个位置可能已有其他数位贡献，先合并旧值再处理进位。
sum := digits[pos] + x*y
digits[pos] = sum % 10
// 高位贡献要累加，不能覆盖此前的进位。
digits[pos-1] += sum / 10
}
}
idx := 0
for idx < len(digits) && digits[idx] == 0 {
idx++
}
ans := make([]byte, 0, len(digits)-idx)
for idx < len(digits) {
ans = append(ans, byte(digits[idx])+'0')
idx++
}
return string(ans)
}
复杂度分析
设两个输入字符串的长度分别为 $m$、$n$。
- 时间复杂度：$O(mn)$。两层循环计算全部 $mn$ 对数位乘积，最后拼接结果需要 $O(m+n)$ 时间。
- 辅助空间复杂度：$O(m+n)$，用于保存结果数位；构造返回字符串所需的空间也是 $O(m+n)$。
关键点总结
[!green]
- 先根据位权确定落点：本位是
i + j + 1，进位是前一位。- 每次乘积都要和该位置已有贡献相加，再拆分本位与进位。
- 从低位向高位处理，保证暂存在高位的进位最终也会被整理成一位数字。
易错点总结
[!yellow]
- 数组需要
m + n个位置；少开一位无法容纳完整乘积，最低位的下标也会越界。- 计算
sum时漏掉digits[pos]，会丢失之前数位对产生的贡献。- 高位必须使用
+=累加；直接赋值会覆盖已有的进位或乘积贡献。- 本实现依赖两层循环都从右向左进行，不能在保持当前进位逻辑的同时随意改成正序。
- 去除前导零时不能把零结果变成空字符串；代码先单独处理零输入，再拼接非零乘积。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 415. 字符串相加 | 简单 | 逐位加法是合并部分乘积的基础，本题还需处理不同乘积对应的位权偏移。 |
| 67. 二进制求和 | 简单 | 同样维护进位，但原题为二进制加法，本题是十进制逐位乘积累加。 |