如何实现LeetCode 43的字符串相乘算法？

## 作用 实现两个以字符串形式表示的非负整数 `num1` 和 `num2` 相乘，并返回字符串形式的乘积，不能直接依赖语言的大整数类型。 ## 原理 ### 1. 使用竖式乘法 - 从右向左遍历两个字符串中的每一位数字。 - 字符转数字时利用 ASCII 码：`num[i] - '0'`。 - 两个长度分别为 `M`、`N` 的数相乘，结果最多有 `M + N` 位，因此可以初始化一个长度为 `M + N` 的结果数组，全部填 `'0'`。 ### 2. 确定每位乘积的位置 对于下标 `i` 和 `j` 上的两个数字： - 个位乘积累计在结果数组的 `i + j + 1` 位置。 - 进位累加到 `i + j` 位置。 计算方式： - `next = 当前结果位 + num1[i] * num2[j]` - 当前位保存 `next % 10`。 - 进位 `next / 10` 加到前一位。 ### 3. 处理前导零 - 所有乘法计算完成后，去掉结果开头的 `0`。 - 如果去掉后为空，说明乘积为 `0`，返回字符串 `"0"`。 ### 参考实现 ```csharp public class Solution { public string Multiply(string num1, string num2) { StringBuilder sum = new StringBuilder(new string('0', num1.Length + num2.Length)); for (int i = num1.Length - 1; i >= 0; i--) { for (int j = num2.Length - 1; j >= 0; j--) { int next = sum[i + j + 1] - '0' + (num1[i] - '0') * (num2[j] - '0'); sum[i + j + 1] = (char)(next % 10 + '0'); sum[i + j] += (char)(next / 10); } } string res = sum.ToString().TrimStart('0'); return res.Length == 0 ? "0" : res; } } ``` ### 复杂度 - 时间复杂度：`O(MN)`，其中 `M`、`N` 分别是两个字符串的长度。 - 空间复杂度：`O(M + N)`，用于保存乘法结果。