字符串相乘
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1
示例 2
模拟答题者思考
1. 我先想暴力：把两个字符串转成 int 再相乘——题面明确禁止，且长度可达 200 位，会溢出。
2. 重复在哪里？竖式乘法里，每一位都要与另一个数的每一位相乘，再把部分积按位对齐相加。这个「对齐 + 进位」过程可以抽象成数组操作。
3. 关键观察：num1[i] × num2[j] 的结果（最多两位）应写入结果数组的 res[i+j+1]（个位）和 res[i+j]（十位进位）。开一个长度 m+n 的数组足够存放最终乘积。
4. 例 "123" × "456"：3×6=18 写入 res[4..5]；3×5=15、2×6=12 等同理累加并进位。全部数位对处理完后，从左到右跳过前导零，拼接成字符串。
5. 特判：任一串为 "0" 直接返回 "0"；结果全零时也要返回 "0" 而非空串。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
m, n | int | 定义：num1、num2 的长度维护：乘积最多 m+n 位，结果数组长度由此确定更新：初始化后不变 |
res | int[] | 定义：长度为 m+n 的数位数组，res[k] 表示乘积从右数第 k 位的数字（低位在右）维护：模拟竖式乘法， num1[i]×num2[j] 的贡献落在 res[i+j] 与 res[i+j+1]更新：每对数位相乘后 res[p2] += mul，再向 res[p1] 传递进位 |
i, j | int | 定义：num1、num2 当前参与相乘的字符下标（从右向左）维护：双重循环枚举所有数位对，覆盖竖式中每一次「个位×个位、个位×十位…」 更新： i 从 m-1 到 0，内层 j 从 n-1 到 0 |
mul | int | 定义：当前两位数字的乘积 int(num1[i]) × int(num2[j])维护：范围 0..81，加上已有低位后可能产生进位更新：每对 (i,j) 重新计算 |
p1, p2 | int | 定义：mul 在 res 中对应的十位、个位下标，p2 = i+j+1、p1 = i+j维护：下标 i 越靠左（高位）、j 越靠左，乘积贡献越靠高位更新：随当前 (i,j) 变化 |
落码步骤
1. 若 num1 == "0" or num2 == "0"，返回 "0"
2. 令 m, n = len(num1), len(num2)，初始化 res = [0] * (m + n)
3. 双重循环：i 从 m-1 到 0，j 从 n-1 到 0
4. 计算 mul = int(num1[i]) * int(num2[j])，p1 = i+j、p2 = i+j+1
5. sum = mul + res[p2]，res[p2] = sum % 10，res[p1] += sum // 10（个位落位、进位向高位传递）
6. 从左到右跳过前导零，将 res 剩余数位拼接为字符串返回
代码实现
class Solution:
def multiply(self, num1: str, num2: str) -> str:
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
# 跳过前导零
start = 0
while start < len(res) - 1 and res[start] == 0:
start += 1
return "".join(str(d) for d in res[start:])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;
}
}
int start = 0;
while (start < (int)res.size() - 1 && res[start] == 0) start++;
string ans;
for (int k = start; k < (int)res.size(); k++)
ans += char('0' + res[k]);
return ans;
}
};
// 时间 O(m×n)，空间 O(m+n)复杂度分析
O(m × n)（m、n 为两串长度，每位与每位相乘一次）
O(m + n)（结果数组长度最多 m+n 位）
常见坑
下标写反：num1[i]×num2[j] 的个位在 res[i+j+1]、十位进位在 res[i+j]，不是 res[i+j] 存个位。
忘记累加已有值：应写 total = mul + res[p2]，该位可能已被之前的数位对贡献过。
前导零处理不当：结果数组首位常为 0，需跳过；但若乘积为 0 必须返回 "0" 而非空字符串。
必测边界 Case
num1 = "0", num2 = "12345" → "0"（任一侧为 0 即返回 "0"）
num1 = "2", num2 = "3" → "6"（最小非平凡输入）
num1 = "99", num2 = "99" → "9801"（中间结果数组有前导零，输出需跳过）
num1 = "1", num2 = "99999999999999999999" → "99999999999999999999"（一位数乘大数）
num1 = "123", num2 = "456" → "56088"