0043. Multiply Strings¶
题目信息¶
- 题号:
字符串相乘
- 难度:
Medium
- 主题:
字符串、竖式乘法、位权对齐、进位
- 原题:
- 重点:
从逐行部分积推导到固定结果槽位,并把乘法贡献与十进制进位分开处理
题目重述¶
给定两个表示非负整数的十进制字符串 num1 和 num2,返回它们乘积的十进制字符串。
不能把整个字符串直接转换成内置整数,也不能使用任意精度整数库。输入只包含字符 '0' 到 '9';除字符串
"0" 外,输入没有前导零,输出也必须使用同样的规范形式。
num1 和 num2 的长度均位于 [1, 200]。
自建示例¶
需要连续进位:
输入:num1 = "99", num2 = "99"
输出:"9801"
解释:四个数字位乘积会汇入相邻槽位,统一进位后得到 9801。
乘积中保留真实的零:
输入:num1 = "1000", num2 = "205"
输出:"205000"
解释:结果中间和末尾的零具有十进制位权,不能删除。
任一因数为零:
输入:num1 = "0", num2 = "873421"
输出:"0"
解释:结果必须规范化为单个字符 "0"。
C++ 实现¶
#include <algorithm>
#include <string>
#include <vector>
class Solution {
private:
std::string addDecimalStrings(
const std::string& first,
const std::string& second
) {
int left = static_cast<int>(first.size()) - 1;
int right = static_cast<int>(second.size()) - 1;
int carry = 0;
std::string sum;
while (left >= 0 || right >= 0 || carry != 0) {
int value = carry;
if (left >= 0) {
value += first[left] - '0';
--left;
}
if (right >= 0) {
value += second[right] - '0';
--right;
}
sum.push_back(static_cast<char>('0' + value % 10));
carry = value / 10;
}
std::reverse(sum.begin(), sum.end());
return sum;
}
std::string multiplyByOneDigit(
const std::string& number,
int digit,
int decimalShift
) {
if (digit == 0) {
return "0";
}
int carry = 0;
std::string product;
for (int index = static_cast<int>(number.size()) - 1;
index >= 0;
--index) {
const int value = (number[index] - '0') * digit + carry;
product.push_back(static_cast<char>('0' + value % 10));
carry = value / 10;
}
if (carry != 0) {
product.push_back(static_cast<char>('0' + carry));
}
std::reverse(product.begin(), product.end());
product.append(decimalShift, '0');
return product;
}
std::string partialProductRows(
const std::string& first,
const std::string& second
) {
if (first == "0" || second == "0") {
return "0";
}
const std::string* multiplicand = &first;
const std::string* multiplier = &second;
if (multiplicand->size() < multiplier->size()) {
std::swap(multiplicand, multiplier);
}
std::string result = "0";
int decimalShift = 0;
for (int index = static_cast<int>(multiplier->size()) - 1;
index >= 0;
--index, ++decimalShift) {
const int digit = (*multiplier)[index] - '0';
const std::string row = multiplyByOneDigit(
*multiplicand,
digit,
decimalShift
);
result = addDecimalStrings(result, row);
}
return result;
}
std::string accumulateBySlots(
const std::string& first,
const std::string& second
) {
if (first == "0" || second == "0") {
return "0";
}
const int firstLength = static_cast<int>(first.size());
const int secondLength = static_cast<int>(second.size());
std::vector<int> slots(firstLength + secondLength, 0);
for (int firstIndex = firstLength - 1; firstIndex >= 0; --firstIndex) {
const int firstDigit = first[firstIndex] - '0';
for (int secondIndex = secondLength - 1;
secondIndex >= 0;
--secondIndex) {
const int secondDigit = second[secondIndex] - '0';
slots[firstIndex + secondIndex + 1] += firstDigit * secondDigit;
}
}
for (int index = firstLength + secondLength - 1; index > 0; --index) {
slots[index - 1] += slots[index] / 10;
slots[index] %= 10;
}
int firstNonZero = 0;
while (firstNonZero < static_cast<int>(slots.size()) &&
slots[firstNonZero] == 0) {
++firstNonZero;
}
std::string result;
for (int index = firstNonZero;
index < static_cast<int>(slots.size());
++index) {
result.push_back(static_cast<char>('0' + slots[index]));
}
return result.empty() ? "0" : result;
}
public:
std::string multiply(std::string num1, std::string num2) {
return accumulateBySlots(num1, num2);
}
};
题解¶
字符串竖式基线¶
长度最多为 200 的十进制字符串远超固定宽度整数。可直接复用小学竖式:每次只计算两个一位数字的乘积,再按照十进制 位权对齐。
partialProductRows 对第二个数从个位向高位扫描。每一位先与完整的第一个数相乘,再按它距离个位的位数补零,最后
把所有部分积逐行相加。例如 314 * 27:
314
× 27
--------
2198
6280
--------
8478
这个方法严格对应手算过程,也不依赖整数范围。它仍会反复创建部分积字符串,并在加入每一行时重新执行十进制加法。 所有一位乘积最终只属于固定的结果位,因此可以直接累加到共享槽位中。
固定槽位模型¶
设两个非零数的长度分别为 m 和 n。它们的乘积小于 10^(m+n),所以最多占 m+n 位。建立长度为
m+n 的整数数组 slots,每个下标代表一个十进制结果位;最高槽位允许为零,对应实际结果只有
m+n-1 位。
first[i] 距离个位有 m-1-i 位,second[j] 距离个位有 n-1-j 位。两个数字位乘积的位权为:
长度为 m+n 的槽位数组中,下标 k 对应位权 10^{m+n-1-k}。令两者相等得到:
因此每一对数字位只需执行:
slots[i + j + 1] += firstDigit * secondDigit;
双重循环恰好访问每一对下标一次,并把它加入唯一的位权槽位。槽位此时可以大于 9,它只是尚未规范化的十进制
系数。
统一进位不变量¶
所有乘法贡献累加完成后,从最右槽位向左处理。对于当前值 value:
保留 value % 10 作为当前位,把 value / 10 加到左侧槽位,表示的总数不变。扫描方向保证当前槽位右侧已经
全部规范化,新增进位只会交给尚未处理的左侧继续传播。
每次迭代后都保持以下状态:
当前槽位及其右侧都位于
0..9;所有槽位共同表示的数值与全部一位乘积之和相同;
尚未处理的左侧槽位可以继续接收进位。
处理到下标 1 后,最左槽位已经合法。乘积最多占 m+n 位,因此不会需要数组之外的新槽位。
状态演化¶
以 99 * 99 为例,四个数字位乘积先得到:
[0, 81, 162, 81]
再从右向左规范化:
处理槽位 |
向左进位 |
当前位保留 |
数组 |
|---|---|---|---|
3 |
8 |
1 |
|
2 |
17 |
0 |
|
1 |
9 |
8 |
|
最终槽位为 [9, 8, 0, 1],得到 "9801"。乘法阶段没有遗漏或重复任何数字位对,进位阶段只改变表示形式,
所以最终字符串与原乘积相同。
输出规范化¶
任一输入为 "0" 时直接返回 "0"。两个非零输入的槽位数组最多只在最高端出现未使用的零,从第一个非零
槽位开始输出即可。
结果内部和末尾的零都对应真实位权。例如 1000 * 205 = 205000,只能跳过最高端的空槽位,不能删除中间或末尾
的零。若最终字符串为空,则乘积为零,统一返回 "0"。
代码演进¶
partialProductRows 完整模拟竖式乘法:逐位生成部分积,再通过字符串加法合并。它建立了不依赖整数类型的正确
基线,但反复分配和扫描中间字符串。
accumulateBySlots 直接按照位权把所有一位乘积累加到长度 m+n 的数组,再统一完成进位和输出。公开入口采用
该方法,因为每个数字位对只计算一次,中间状态也始终保存在固定槽位中。
复杂度分析¶
设两个字符串长度为 m 和 n。部分积方法执行 O(mn) 次一位乘法,还会反复创建并相加长度至多
m+n 的字符串。
主方法访问全部 mn 对数字位,再用 O(m+n) 时间统一进位和输出,总时间为 O(mn)。结果槽位数组与输出
字符串均占 O(m+n) 空间。