字符串相乘

这是一道围绕字符串展开的高频练习。建议先掌握「竖式模拟」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

题目分析

这道题表面上是在处理「字符串相乘」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考字符串这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：按照竖式乘法逐位相乘，把乘积累加到结果数组对应的位置上，再统一处理进位。

推荐代码

推荐解法：竖式模拟

时间复杂度： O(mn)

空间复杂度： O(m+n)

核心思路：按照竖式乘法逐位相乘，把乘积累加到结果数组对应的位置上，再统一处理进位。

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 p1 = i + j;
                int p2 = i + j + 1;
                int sum = digits[p2] + x * y;
                digits[p2] = sum % 10;
                digits[p1] += sum / 10;
            }
        }

        StringBuilder builder = new StringBuilder();
        for (int digit : digits) {
            if (builder.length() == 0 && digit == 0) {
                continue;
            }
            builder.append(digit);
        }
        return builder.toString();
    }
}

结构化讲解

面试时怎么讲

开场思路

这题不能转大整数，我会直接模拟竖式乘法。

核心过程

先开一个长度为 m+n 的结果数组。
从右往左枚举两数的每一位，把乘积累加到对应位置。
每次都把当前位留在后一个格子，把进位加到前一个格子。
最后跳过前导零，把数组转成字符串。

复杂度总结

时间复杂度 O(mn)，空间复杂度 O(m+n)。

面试补一句：这题最容易讲清楚的点，是“乘积落点为什么是 i+j 和 i+j+1”。

核心思路

不能把字符串直接转整数时，最自然的办法就是模拟小学竖式乘法。第 i 位和第 j 位的乘积，会落在结果数组的固定两格里。

步骤讲解

先开结果数组

长度最多是 m + n，足够容纳所有乘积和进位。

为什么这样做：两个数分别有 m、n 位，相乘后的位数最多就是 m+n。

对应代码提示：int[] digits = new int[m + n];

逐位相乘并累加

从低位往高位枚举，乘积加到 i+j+1 和 i+j 对应的位置。

为什么这样做：这正是竖式乘法里个位和进位的落点。

对应代码提示：int sum = digits[p2] + x * y;

跳过前导零后拼接答案

结果数组可能有一个前导 0，拼接时需要跳过。

为什么这样做：例如 99 * 99 = 9801，结果长度不一定占满 m+n。

对应代码提示：if (!(builder.length() == 0 && digit == 0)) { ... }

易错点

乘积位置放错一位

很多人知道要放两格，但会把 i+j 和 i+j+1 写反。

正确理解：固定记忆：p2 放当前位，p1 放进位。

没有处理结果全为 0

输入中有 0 时，拼接后可能得到空串。

正确理解：开头单独判断任一字符串是否等于 0。

复杂度与适用判断

时间复杂度：O(mn)

空间复杂度：O(m+n)

比其他方案更好在哪里：比反复做字符串加法更直接，且更容易控制复杂度。

适用判断：大整数运算被禁止时，优先考虑数组模拟竖式。

额外提醒

结果数组不是存字符，而是先存每一位的累积值。