1. 问题分析与初始思路
力扣第43题"字符串相乘"是一个经典的算法问题，要求我们实现两个用字符串表示的大数相乘，并以字符串形式返回结果。这个问题看似简单，但隐藏着几个关键挑战：
- 大数处理：当数字非常大时（比如100位），直接转换成整数会导致溢出
- 字符串操作：需要手动实现每一位的乘法和加法运算
- 进位处理：正确处理乘法过程中的进位是难点
- 前导零处理：需要去除结果中不必要的前导零
我最初尝试的解法（如用户提供的代码）是直接将字符串转换为整数相乘后再转回字符串。这种方法虽然在小数字情况下可行，但完全违背了题目"不能使用内置BigInteger库或直接转换"的要求，也无法处理大数情况。
2. 正确解法思路解析
2.1 模拟竖式乘法
正确的解法是模拟我们小学学过的竖式乘法。具体步骤：
- 初始化一个足够大的结果数组（长度为num1.length + num2.length）
- 从右到左遍历两个数字的每一位
- 将num1的第i位与num2的第j位相乘，结果加到结果数组的i+j+1位置
- 处理所有进位
- 将结果数组转换为字符串，去除前导零
这个方法的优势在于：
- 完全避免了数字转换，纯字符串操作
- 时间复杂度为O(m*n)，m和n分别是两个数字的长度
- 空间复杂度为O(m+n)，符合题目要求
2.2 关键实现细节
cpp复制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 sum = mul + res[i + j + 1];
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}
string ans;
for (int num : res) {
if (!ans.empty() || num != 0) {
ans.push_back(num + '0');
}
}
return ans.empty() ? "0" : ans;
}
3. 代码实现详解
3.1 初始化处理
首先处理特殊情况：如果任一数字为"0"，结果直接返回"0"。这可以避免后续不必要的计算。
cpp复制if (num1 == "0" || num2 == "0") return "0";
3.2 结果数组初始化
我们创建一个大小为m+n的数组来存储中间结果。这是因为两个长度分别为m和n的数字相乘，结果长度最多为m+n。
cpp复制vector<int> res(m + n, 0);
3.3 双重循环计算乘积
外层循环遍历num1的每一位，内层循环遍历num2的每一位。注意我们是从最低位（字符串末尾）开始计算。
cpp复制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 sum = mul + res[i + j + 1];
// 更新当前位和下一位
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
}
3.4 处理前导零
最后我们需要将结果数组转换为字符串，并跳过前导零。如果结果全为零，则返回"0"。
cpp复制string ans;
for (int num : res) {
if (!ans.empty() || num != 0) {
ans.push_back(num + '0');
}
}
return ans.empty() ? "0" : ans;
4. 常见问题与优化技巧
4.1 为什么结果数组大小是m+n？
两个数相乘的最大位数是它们位数之和。例如：
- 99×99=9801（2位×2位=4位）
- 100×100=10000（3位×3位=5位）
4.2 如何处理进位？
在计算过程中，我们同时处理了乘积和进位。具体来说：
- 计算当前位的乘积
- 加上之前可能存在的进位
- 当前位保留sum%10
- 进位部分加到前一位(sum/10)
4.3 边界条件测试用例
测试时应特别注意以下情况：
- 输入包含"0"的情况
- 输入包含前导零的情况（虽然题目说输入不含前导零）
- 两个大数相乘（如50位×50位）
- 两个单数字符串相乘
4.4 性能优化建议
- 如果其中一个数字为"1"，可以直接返回另一个数字
- 可以预先计算数字中'0'的数量，快速判断结果是否为"0"
- 使用更高效的数据结构（如原生数组）可能比vector更快
5. 算法复杂度分析
- 时间复杂度：O(m×n)，其中m和n分别是两个数字的长度。我们需要对每对数字位执行乘法运算。
- 空间复杂度：O(m+n)，用于存储中间结果。
6. 实际编码中的坑与教训
- 字符与数字转换：容易忘记减去'0'来获取数字值
- 数组越界：在更新res[i+j]时可能越界，但在这个算法中不会发生
- 前导零处理：容易遗漏全零情况的处理
- 进位顺序：必须先处理低位再处理高位
我在最初实现时犯的一个典型错误是：
cpp复制// 错误示例：进位处理顺序不对
res[i + j + 1] = sum % 10;
res[i + j] = sum / 10; // 这里应该是+=而不是=
正确的做法是使用+=来累加进位，因为同一个位置可能被多次访问。
7. 扩展思考
7.1 其他实现方法
除了竖式乘法，还可以使用：
- Karatsuba算法：更高效的大数乘法算法，时间复杂度约为O(n^1.585)
- FFT-based乘法：利用快速傅里叶变换实现，时间复杂度O(n log n)
但这些方法实现复杂，在面试或竞赛中，竖式乘法通常是更实用的选择。
7.2 相关题目练习
为了巩固这个概念，建议尝试以下力扣题目：
- 字符串相加（力扣415）
- 二进制求和（力扣67）
- 加一（力扣66）
- 数组形式的整数加法（力扣989）
8. 个人实现心得
在实际编码过程中，我发现以下几点特别重要：
- 画图辅助：在纸上画出竖式乘法的过程，有助于理解算法
- 分步调试：特别是处理进位时，逐步跟踪变量变化
- 测试用例：要包含各种边界情况，特别是全零和大数情况
- 代码简洁：保持代码清晰易读，避免过度优化导致可读性下降
经过多次练习后，我对字符串操作和进位处理有了更深的理解。这类题目看似简单，但要写出健壮、高效的代码，需要反复练习和思考。