如何实现字符串形式的大数相乘？（LeetCode 43）

简化版

字符串相乘不能转整数，应该模拟竖式乘法。若 num1[i] 和 num2[j] 相乘，它们的结果会影响结果数组中的 i+j+1 位，进位影响 i+j 位。用长度为 m+n 的数组累计乘积，最后跳过前导零并拼成字符串。时间 O(mn)，空间 O(m+n)。

详细版

String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) return "0";
    int m = num1.length(), n = num2.length();
    int[] res = new int[m + n];
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            int sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    StringBuilder sb = new StringBuilder();
    int k = 0;
    while (k < res.length && res[k] == 0) k++;
    while (k < res.length) sb.append(res[k++]);
    return sb.toString();
}

结果最多有 m+n 位，例如 99*99=9801。
个位乘积落在 i+j+1，进位落在 i+j。
不能忘记处理 "0"，否则跳过前导零后可能返回空串。

完整版教学

一、为什么不能直接转数字

题目中的数字字符串可能非常长，超过 int、long 甚至普通大整数限制。要求通常还禁止直接使用大整数库，所以必须把字符串当成数字位数组，模拟人手算乘法。

这和字符串相加同源：相加是一位对一位加，乘法是每一位和另一串的每一位相乘，再把贡献累加到对应位置。核心都是“逐位模拟 + 处理进位”。

二、结果数组长度为什么是 m+n

两个长度分别为 m、n 的非负整数相乘，结果位数最多是 m+n。例如：

99 * 99 = 9801，2 位 * 2 位 -> 最多 4 位
123 * 45 = 5535，3 位 * 2 位 -> 最多 5 位

所以可以提前开 int[] res = new int[m+n]。即使最高位没有用上，最后跳过前导零即可。

三、下标关系 i+j 和 i+j+1 怎么来的

假设字符串下标从左到右，num1[i] 是第 m-1-i 个低位，num2[j] 是第 n-1-j 个低位。两位相乘后，低位位置相加，最终落到结果数组靠右的对应位置。常用记法是：

num1[i] * num2[j] 的个位贡献 -> res[i+j+1]
进位贡献                     -> res[i+j]

以 123 * 45 为例，3 和 5 相乘得到 15，个位 5 放到最右端，进位 1 放到左一位。这正对应 i+j+1 和 i+j。

记忆钩子：两位相乘先落到右边的 i+j+1，满 10 的进位推到左边的 i+j。

四、用 123*45 手推一遍

结果数组长度是 5，初始为 [0,0,0,0,0]。

3*5=15 -> res[4]=5, res[3]+=1
3*4=12，加 res[3] 原有 1 -> 13，res[3]=3, res[2]+=1
2*5=10，加 res[3] 原有 3 -> 13，res[3]=3, res[2]+=1
...
最终得到 [0,5,5,3,5] -> "5535"

真实代码中不需要显式列竖式，双重循环会把每个乘积贡献累加到结果数组，数组负责承接所有进位。

五、和逐行部分积相加的对比

方法	思路	复杂度	实现难点
部分积字符串相加	每一位生成一行乘积，再累加	O(mn + 行数相加成本)	代码长，补零多
结果数组累加	每个 digit 乘积直接落位	O(mn)	要记住 `i+j+1`
转大整数	使用库或内置大数	取决于库	通常不符合题目要求

数组落位法是面试最常见写法，因为它把竖式乘法压缩成固定下标规则。

六、边界和前导零

如果任意一个输入是 "0"，直接返回 "0"。否则最终数组可能有前导 0，例如 12*3=36，结果数组长度 3，可能是 [0,3,6]，拼接时要跳过第一个 0。

输入通常保证没有前导零，除非数字本身就是 "0"。如果业务输入可能有前导零，最好先规范化输入，避免 "0002"* "03" 这类情况影响输出格式。

七、常见误区与追问

误区：把字符串转成 long 后相乘。 大数会溢出，也违背题意。
误区：结果数组只开 max(m,n)。 乘积最多有 m+n 位，数组会不够。
误区：把个位放到 i+j。 正确是个位落 i+j+1，进位落 i+j。
追问：为什么最后要跳过前导零？ 预留的最高位不一定被使用，直接拼会得到 "05535"。
追问：能处理负数吗？ 原题是非负数字；若扩展到负数，需要先处理符号，再对绝对值相乘。
追问：和字符串相加有什么联系？ 都是竖式模拟；相乘可以看成多次单 digit 乘法与进位累加。

八、加强记忆

字符串相乘 = 竖式乘法数组化。开 m+n 长度结果数组，num1[i]*num2[j] 的个位落 res[i+j+1]，进位加到 res[i+j]。双重循环累计所有位贡献，最后跳过前导零。最关键的下标口诀是：个位右一格，进位左一格。

简化版

详细版