43. 字符串相乘（Multiply Strings）

频次 ★★★ · 难度 🟡 · 高频：腾讯/字节

题目

给定两个非负整数（以字符串形式给出），计算它们的乘积并同样以字符串形式返回。不能使用 BigInteger 或直接将输入转为整数。

示例：

输入: "2", "3"
输出: "6"

输入: "123", "456"
输出: "56088"

思路

模拟竖式乘法：一个长度为 m 的数乘以长度为 n 的数，结果最多 m + n 位。用一个 int 数组 res 记录每一位的结果，两层循环：num1[i] * num2[j] 的结果放在 res[i + j]（高位）和 res[i + j + 1]（低位）。最后去除前导零拼成字符串。

代码

public 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--) {
        int a = num1.charAt(i) - '0';
        for (int j = n - 1; j >= 0; j--) {
            int b = num2.charAt(j) - '0';
            int sum = a * b + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
 
    StringBuilder sb = new StringBuilder();
    for (int d : res) {
        if (sb.length() == 0 && d == 0) continue;
        sb.append(d);
    }
    return sb.toString();
}

复杂度

• 时间：O(m × n) — 两层循环遍历所有数字对
• 空间：O(m + n) — 结果数组

边界条件

• 任一个为 "0"：直接返回 "0"，避免前导零处理。
• 大数相乘：m、n 可达上百位，必须用数组/字符串模拟，不能用整型溢出。
• 一位数乘多位数：属于竖式乘法的退化情况，算法同样工作。

变式

• 字符串相加（415. 字符串相加）：加法比乘法简单，只有一维进位，没有错位累加。
• 大整数加/减/乘/除的完整实现：乘法是中间步骤，加减是基础，除法（高精度除低精度或高精度除高精度）更复杂。
• 链表版加法（2. 两数相加）：逆序存储省去了翻转。

易错点

• 结果位数误判为 m × n：两个数相乘最大 m + n 位（如 9×9=81 是 2 位），数组要开 m + n。
• 进位累加顺序：res[i + j + 1] 存个位（低位），res[i + j] 存十位（高位），两个位置的修改方式不同——低位直接赋值，高位累加（因为高位可能被多轮乘积贡献）。
• 前导零过滤：用 sb.length() == 0 && d == 0 跳过开头的零，但不能跳过中间零（如 "1001" 中的 "00"）。

面试追问

• 如何优化到接近 O(n^1.58)？ 用 Karatsuba 分治乘法，把大数分成高低位，减少乘法次数，面试一般不要求实现但要知道存在更快的算法。
• 如果去掉”不能用 BigInteger”的限制，Python 和 Java 怎么直接算？ Python 的 int 原生支持任意精度；Java 用 BigInteger，内部也是用类似的 int 数组模拟，只不过用了更优化的基（和更复杂的乘法算法）。

关联题

• 同套路：415. 字符串相加（加法）、66. 加一（数组版）
• 进阶：2. 两数相加（链表版大数加法）
• 知识点：大数模拟是”竖式计算”在程序中的映射，任意进制加法/乘法都可用此骨架