字符串相乘 图解题解

这道题到底在问什么

num1,num2

"123","456"

输出

"56088"

先想最直接的笨办法

最直觉的笨办法：转成整数相乘再转回字符串。可题目里数字可能上百位，远超 long 的范围，一转就溢出、算出来是错的——所以只能逐位手算。（动画第 3 步）

最优解：一步一步想明白

1. 3最直觉的笨办法：转成整数相乘再转回字符串。可题目里数字可能上百位，远超 long 的范围，一转就溢出、算出来是错的——所以只能逐位手算。
2. 4不能转 int(会溢出)既然不能转整数，就回到小学竖式：每一位分别相乘，再把每次的小结果按位置累加、处理进位。
3. 5长度 m+n，全置 0先想清楚结果有多长：m 位数乘 n 位数，最多 m+n 位。所以开一个长度 6 的数组(123、456 各 3 位)，每个格子先放 0，用来逐位累加。
4. 6积放到结果的 i+j 与 i+j+1竖式的核心规律：num1 的第 i 位 × num2 的第 j 位，乘积最多两位——个位落在结果的第 i+j+1 位，进位落在它左边的第 i+j 位。记住这个下标对应，就不会算错位置。
5. 7个位 8 → 第 5 位，进位 1 → 第 4 位举个例子：个位 3 × 个位 6 = 18。按规律，8 放到第 5 位、进位 1 加到第 4 位。其余八对数字(1·2·3 × 4·5·6 共 9 对)都这样乘、累加进对应格子。
6. 8第 4 位已有进位 1，再被 3×5=15 砸关键来了：接着算 3 × 5 = 15，它的个位也要落到第 4 位。可第 4 位刚才已被 3×6 的进位 1 占住——这一格要被第二对数字继续累加，不能直接覆盖。
7. 9total=15+旧值1=16 → 第4位留6、进位1给第3位正确做法：先把新积 15 和这格旧值 1 相加得 total=16，再拆——个位 6 留在第 4 位、进位 1 送到第 3 位。这就是「先累加再取模」：旧的进位 1 没被冲掉，而是被一起算了进去。数组从 [0,0,0,0,1,8] 变成 [0,0,0,1,6,8]。
8. 10所有 i×j 累加，满十进位把 3 位 × 3 位共 9 对都乘一遍，每次都累加到对应位、满十就往前一位进。全部算完，结果数组是 [0,5,6,0,8,8]。
9. 11[0,5,6,0,8,8] → "56088"最后把数组拼成字符串，跳过开头多余的 0(若结果就是 0 要保留一个)，得到 "56088"——正是 123 × 456。
10. 14一句话本质：num1[i] × num2[j] 的两位结果，个位累加到 i+j+1、进位累加到 i+j，全部乘完再去前导 0。下标对应记牢，这题就稳了。
11. 16第 4 位先被进位 1、又被 3×5=15 砸为什么强调「先累加再取模」？看第 4 位：3×6 时它先被进位 1 占住。随后 3×5=15 落到第 4 位，加上原有进位 1 变成 16——必须 total = 新积 + 这格旧值 再拆个位/进位(留 6、进 1)，否则旧的 1 就被冲掉、结果错。
12. 22这题是「字符串大数运算」的原子操作。同骨架可迁移：LC415 字符串相加(只剩一层进位)、LC2 两数相加(链表版竖式)、LC67 二进制求和(进位阈值变 2)。想成体系刷可去 /leetcode-animation/ds?k=math 跟专题，或问 AI 助教「竖式模拟还有哪些变体」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def multiply(self, num1, num2):
        if num1 == '0' or num2 == '0':
            return '0'
        m, n = len(num1), len(num2)
        res = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                p1, p2 = i + j, i + j + 1
                total = mul + res[p2]
                res[p2] = total % 10
                res[p1] += total // 10
        return ''.join(map(str, res)).lstrip('0') or '0'

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        int m = num1.size(), n = num2.size();
        vector<int> res(m + n, 0);
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i]-'0') * (num2[j]-'0');
                int p1 = i + j, p2 = i + j + 1;
                int total = mul + res[p2];
                res[p2] = total % 10;
                res[p1] += total / 10;
            }
        string s;
        for (int x : res) if (!(s.empty() && x == 0)) s += char('0' + x);
        return s.empty() ? "0" : s;
    }
};

class Solution {
    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--)
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
                int p1 = i + j, p2 = i + j + 1;
                int total = mul + res[p2];
                res[p2] = total % 10;
                res[p1] += total / 10;
            }
        StringBuilder sb = new StringBuilder();
        for (int x : res) if (!(sb.length() == 0 && x == 0)) sb.append(x);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

# 大数竖式骨架：定位 i+j/i+j+1，先累加再拆进位
res = [0] * (len(A) + len(B))   # 1) 结果至多 m+n 位
for i in range(len(A) - 1, -1, -1):    # 从低位往高位
    for j in range(len(B) - 1, -1, -1):
        total = digit(A, i) * digit(B, j) + res[i + j + 1]
        res[i + j + 1] = total % 10   # 2) 个位留在 i+j+1
        res[i + j]    += total // 10  # 3) 进位送到 i+j
return strip_leading_zero(res)   # 4) 去前导 0，但别删光

// 大数竖式骨架：定位 i+j/i+j+1，先累加再拆进位
vector<int> res(A.size() + B.size(), 0);   // 1) 至多 m+n 位
for (int i = A.size()-1; i >= 0; --i)      // 从低位往高位
  for (int j = B.size()-1; j >= 0; --j) {
    int total = digit(A,i) * digit(B,j) + res[i+j+1];
    res[i+j+1] = total % 10;   // 2) 个位留 i+j+1
    res[i+j]  += total / 10;   // 3) 进位送 i+j
  }
return stripLeadingZero(res);  // 4) 去前导 0，但别删光

// 大数竖式骨架：定位 i+j/i+j+1，先累加再拆进位
int[] res = new int[A.length() + B.length()];  // 1) 至多 m+n 位
for (int i = A.length()-1; i >= 0; i--)        // 从低位往高位
  for (int j = B.length()-1; j >= 0; j--) {
    int total = digit(A,i) * digit(B,j) + res[i+j+1];
    res[i+j+1] = total % 10;   // 2) 个位留 i+j+1
    res[i+j]  += total / 10;   // 3) 进位送 i+j
  }
return stripLeadingZero(res);  // 4) 去前导 0，但别删光

复杂度

面试官可能追问