43. 字符串相乘
题目描述
输入两个用字符串表示的非负整数 num1 和 num2。
计算它们的乘积，并同样以字符串形式返回。
不能使用内置的大整数库（如 BigInteger），也不能直接把输入字符串转成整数再计算。
示例 1
输入：num1 = "2", num2 = "3" 输出："6"
解释：2 × 3 = 6。
示例 2
输入：num1 = "123", num2 = "456" 输出："56088"
解释：123 × 456 = 56088。
数据范围
1 <= num1.length, num2.length <= 200num1和num2只含数字字符。- 除了数字 0 本身，两个数都没有前导零。
解题思路：按位相乘累加到结果数组
模拟竖式乘法。长 m 和 n 的两个数相乘，结果至多 m+n 位，开一个 res 数组。num1[i] × num2[j] 的乘积落在 res[i+j]（十位）和 res[i+j+1]（个位）上。从低位到高位枚举每一对数字：把乘积加上 res[i+j+1] 原有的值，个位写回 res[i+j+1]，进位加到 res[i+j]。最后去掉前导 0（至少保留一位）。
为什么正确
处理完若干对 (i, j) 后，把 res 当作一个十进制数来读（允许某些位暂时 ≥ 10），它等于已处理的部分积之和。
复杂度分析
时间 O(m·n)；空间 O(m+n)。
易错点
乘积要加上 res[i+j+1] 原有的值再拆个位和进位，否则会丢掉前面累加的结果。去前导 0 时要至少保留一位，否则 "0" × "52" 会返回空串。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
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):
p = int(num1[i]) * int(num2[j]) + res[i + j + 1]
res[i + j + 1] = p % 10
res[i + j] += p // 10
k = 0
while k < m + n - 1 and res[k] == 0:
k += 1
return ''.join(map(str, res[k:]))class Solution {
public String multiply(String num1, String num2) {
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 p = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + res[i + j + 1];
res[i + j + 1] = p % 10;
res[i + j] += p / 10;
}
}
int k = 0;
while (k < m + n - 1 && res[k] == 0) {
k++;
}
StringBuilder sb = new StringBuilder();
for (int t = k; t < m + n; t++) sb.append(res[t]);
return sb.toString();
}
}class Solution {
public:
string multiply(string num1, string num2) {
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 p = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1];
res[i + j + 1] = p % 10;
res[i + j] += p / 10;
}
}
int k = 0;
while (k < m + n - 1 && res[k] == 0) {
k++;
}
string out;
for (int t = k; t < m + n; t++) out += char('0' + res[t]);
return out;
}
};func multiply(num1 string, num2 string) string {
m, n := len(num1), len(num2)
res := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
p := int(num1[i]-'0')*int(num2[j]-'0') + res[i+j+1]
res[i+j+1] = p % 10
res[i+j] += p / 10
}
}
k := 0
for k < m+n-1 && res[k] == 0 {
k++
}
out := make([]byte, 0, m+n-k)
for t := k; t < m+n; t++ {
out = append(out, byte('0'+res[t]))
}
return string(out)
}var multiply = function(num1, num2) {
const m = num1.length, n = num2.length;
const res = new Array(m + n).fill(0);
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const p = (+num1[i]) * (+num2[j]) + res[i + j + 1];
res[i + j + 1] = p % 10;
res[i + j] += Math.floor(p / 10);
}
}
let k = 0;
while (k < m + n - 1 && res[k] === 0) {
k++;
}
return res.slice(k).join('');
};function multiply(num1: string, num2: string): string {
const m = num1.length, n = num2.length;
const res = new Array<number>(m + n).fill(0);
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const p = (+num1[i]) * (+num2[j]) + res[i + j + 1];
res[i + j + 1] = p % 10;
res[i + j] += Math.floor(p / 10);
}
}
let k = 0;
while (k < m + n - 1 && res[k] === 0) {
k++;
}
return res.slice(k).join('');
}其他解法
竖式加法先算整行部分积，再逐行相加；按位相乘法利用“第 i 位 × 第 j 位只影响结果第 i+j、i+j+1 位”的规律，省去中间字符串，常数更小。
解法 2：竖式逐行相乘再做字符串加法 时间 O(mn + n²)，空间 O(m+n)
完全模拟手算竖式：从右往左取 num2 的每一位 y，用 num1 乘以这一位得到一行部分积（带进位），并在末尾补上与该位位置对应个数的 0。再用第 415 题的“字符串相加”把这一行加到累计答案上。任一数为 "0" 时直接返回 "0"，避免出现前导零。
和手算过程一一对应，最容易理解，并且复用了字符串加法。缺点是每一行都要生成新字符串并做一次完整的加法，补零和反复拼接带来额外的 O(n²) 开销和常数；主解法把 num1[i]×num2[j] 直接累加到结果数组的 i+j 和 i+j+1 位置，只遍历一次。
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
def add(a, b):
i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
while i >= 0 or j >= 0 or carry:
x = int(a[i]) if i >= 0 else 0
y = int(b[j]) if j >= 0 else 0
s = x + y + carry
out.append(str(s % 10))
carry = s // 10
i -= 1
j -= 1
return ''.join(reversed(out))
ans = "0"
m, n = len(num1), len(num2)
for j in range(n - 1, -1, -1):
y = int(num2[j])
cur = ['0'] * (n - 1 - j)
carry = 0
for i in range(m - 1, -1, -1):
p = int(num1[i]) * y + carry
cur.append(str(p % 10))
carry = p // 10
if carry:
cur.append(str(carry))
ans = add(ans, ''.join(reversed(cur)))
return ansclass Solution {
String add(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder out = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int s = x + y + carry;
out.append(s % 10);
carry = s / 10;
i--; j--;
}
return out.reverse().toString();
}
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) return "0";
int m = num1.length(), n = num2.length();
String ans = "0";
for (int j = n - 1; j >= 0; j--) {
int y = num2.charAt(j) - '0';
StringBuilder cur = new StringBuilder();
for (int k = 0; k < n - 1 - j; k++) cur.append('0');
int carry = 0;
for (int i = m - 1; i >= 0; i--) {
int p = (num1.charAt(i) - '0') * y + carry;
cur.append(p % 10);
carry = p / 10;
}
if (carry != 0) cur.append(carry);
ans = add(ans, cur.reverse().toString());
}
return ans;
}
}class Solution {
public:
string add(const string& a, const string& b) {
int i = a.size() - 1, j = b.size() - 1, carry = 0;
string out;
while (i >= 0 || j >= 0 || carry) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int s = x + y + carry;
out.push_back('0' + s % 10);
carry = s / 10;
i--; j--;
}
reverse(out.begin(), out.end());
return out;
}
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int m = num1.size(), n = num2.size();
string ans = "0";
for (int j = n - 1; j >= 0; j--) {
int y = num2[j] - '0';
string cur(n - 1 - j, '0');
int carry = 0;
for (int i = m - 1; i >= 0; i--) {
int p = (num1[i] - '0') * y + carry;
cur.push_back('0' + p % 10);
carry = p / 10;
}
if (carry) cur.push_back('0' + carry);
reverse(cur.begin(), cur.end());
ans = add(ans, cur);
}
return ans;
}
};func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
reverseBytes := func(b []byte) {
for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
b[l], b[r] = b[r], b[l]
}
}
add := func(a, b string) string {
i, j, carry := len(a)-1, len(b)-1, 0
out := []byte{}
for i >= 0 || j >= 0 || carry > 0 {
x, y := 0, 0
if i >= 0 {
x = int(a[i] - '0')
}
if j >= 0 {
y = int(b[j] - '0')
}
s := x + y + carry
out = append(out, byte('0'+s%10))
carry = s / 10
i--
j--
}
reverseBytes(out)
return string(out)
}
m, n := len(num1), len(num2)
ans := "0"
for j := n - 1; j >= 0; j-- {
y := int(num2[j] - '0')
cur := make([]byte, 0, m+n)
for k := 0; k < n-1-j; k++ {
cur = append(cur, '0')
}
carry := 0
for i := m - 1; i >= 0; i-- {
p := int(num1[i]-'0')*y + carry
cur = append(cur, byte('0'+p%10))
carry = p / 10
}
if carry > 0 {
cur = append(cur, byte('0'+carry))
}
reverseBytes(cur)
ans = add(ans, string(cur))
}
return ans
}var multiply = function(num1, num2) {
if (num1 === '0' || num2 === '0') return '0';
const add = (a, b) => {
let i = a.length - 1, j = b.length - 1, carry = 0;
const out = [];
while (i >= 0 || j >= 0 || carry) {
const x = i >= 0 ? a.charCodeAt(i) - 48 : 0;
const y = j >= 0 ? b.charCodeAt(j) - 48 : 0;
const s = x + y + carry;
out.push(s % 10);
carry = Math.floor(s / 10);
i--; j--;
}
return out.reverse().join('');
};
const m = num1.length, n = num2.length;
let ans = '0';
for (let j = n - 1; j >= 0; j--) {
const y = num2.charCodeAt(j) - 48;
const cur = new Array(n - 1 - j).fill(0);
let carry = 0;
for (let i = m - 1; i >= 0; i--) {
const p = (num1.charCodeAt(i) - 48) * y + carry;
cur.push(p % 10);
carry = Math.floor(p / 10);
}
if (carry) cur.push(carry);
ans = add(ans, cur.reverse().join(''));
}
return ans;
};function multiply(num1: string, num2: string): string {
if (num1 === '0' || num2 === '0') return '0';
const add = (a: string, b: string): string => {
let i = a.length - 1, j = b.length - 1, carry = 0;
const out: number[] = [];
while (i >= 0 || j >= 0 || carry) {
const x = i >= 0 ? a.charCodeAt(i) - 48 : 0;
const y = j >= 0 ? b.charCodeAt(j) - 48 : 0;
const s = x + y + carry;
out.push(s % 10);
carry = Math.floor(s / 10);
i--; j--;
}
return out.reverse().join('');
};
const m = num1.length, n = num2.length;
let ans = '0';
for (let j = n - 1; j >= 0; j--) {
const y = num2.charCodeAt(j) - 48;
const cur: number[] = new Array(n - 1 - j).fill(0);
let carry = 0;
for (let i = m - 1; i >= 0; i--) {
const p = (num1.charCodeAt(i) - 48) * y + carry;
cur.push(p % 10);
carry = Math.floor(p / 10);
}
if (carry) cur.push(carry);
ans = add(ans, cur.reverse().join(''));
}
return ans;
}