字符串相乘算法详解：从竖式乘法到LeetCode 43题

字符串相乘，更准确地说就是 LeetCode 43 题 Multiply Strings。我这两年面人时没少出这道题，也反复在刷题群里看人讨论，真正能一次写对、边界全过、说出原理的候选人确实不多。大多数人看到题的第一反应是“直接用 int 转一下不就行了”，然后被一句“输入可能长达 200 位”噎住。这篇文章想从面试官和刷题人两个视角，把这道题背后的竖式乘法原理、两种主流实现、边界处理，以及从字符串乘法延伸出去的大数运算体系，一次性讲透。不管你是刚接触算法题的新手，还是准备跳槽的老兵，看完应该都能对这类“模拟手算”的题目有更立体的理解。

1. 题目拆解：这道题到底在考什么

1.1 先看题面：为什么不能直接转整数

题目描述很简单：给定两个以字符串形式表示的非负整数num1和num2，返回它们的乘积，结果也用字符串表示。要求不能使用任何内置的大整数库，也不能直接把输入字符串转成整数运算。

这里有个很容易被忽略的考点：语言内置的整数类型是有上限的。比如 Java 的int最大约 21 亿，long最大约 9.2 乘以 10 的 18 次方；Python 的int虽然是无限精度，但题目偏不让你用。如果输入是两位 100 位的数字，你无论用什么原生整数类型都装不下。

所以这道题真正考察的东西，说出来其实很朴素：你会不会把小学数学的竖式乘法，翻译成代码逻辑。它考察的不是高深的算法，而是基本的字符串处理、数组操作、进位处理和边界意识。这类题在面试中的出现频率极高，因为它能快速筛掉两类人：一类是只会调库、不懂底层原理的“API 调用师”，另一类是粗心大意、边界情况处理不干净的“差不多先生”。

1.2 核心数学模型：手工竖式的程序化

回忆一下小学学的竖式乘法：假设计算 456 乘以 123，你不会直接去背 456 乘 123 的口诀，而是先算 456 乘 3，再算 456 乘 20，再算 456 乘 100，最后把三次结果错位相加。

用更公式化的语言描述：把num1的第i位数字记为a_i，num2的第j位数字记为b_j，则a_i * b_j在最终结果中所处的位置，取决于这两个数字各自所在的十进制位。如果两个数字的位数分别是m和n，那么乘法的结果位数最多是m + n位，最少是m + n - 1位。

这个“结果位数最多是 m+n 位”的结论，是整个代码实现的基石。比如 99 乘 99 等于 9801，是 4 位，正好是 2 + 2；而 10 乘 10 等于 100，只有 3 位。理解了这一点，你就知道为什么很多标准解法会预先分配一个长度为m + n的数组存结果。

理解了数学原理，接下来就是怎么把竖式逻辑变成代码。这一步有两条路线，一条是“一步到位”的做法，另一条是“先乘后进位”的直译版，我们逐一看。

2. 两种主流实现：卷积法与竖式模拟

2.1 卷积法：一次遍历，同步完成累加与进位

我先给出我最推荐掌握的写法，很多刷题社区的“标准答案”也是长这样：

def multiply(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 = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) p1, p2 = i + j, i + j + 1 total = mul + res[p2] res[p1] += total // 10 res[p2] = total % 10 start = 0 while start < m + n and res[start] == 0: start += 1 return ''.join(map(str, res[start:]))

这段代码的核心逻辑在两层循环里。外层从num1的最低位开始，内层从num2的最低位开始，也就是从右往左逐位相乘。p1是乘积结果的高位位置，p2是低位位置。为什么p2 = i + j + 1？因为num1[i]和num2[j]分别处在不同的十进制位上，它们的乘积落在结果数组里，最低位就是i + j + 1这个位置。

举个例子验证一下：计算 123 乘以 45，结果是 5535。初始化res = [0, 0, 0, 0, 0]。当i = 2（数字 3）、j = 1（数字 5）时，mul = 15，p1 = 3，p2 = 4，把 15 拆成十位 1 和个位 5，个位放进res[4]，十位加到res[3]。接下来i = 2、j = 0（数字 4），mul = 12，此时res[3]已经有 1，total = 12 + 1 = 13，于是res[3]变成 3，res[2]加 1。这样循环走完，res会变成[0, 5, 5, 3, 5]，去掉前导零就是 5535。

这个方法妙在哪儿？它把“累加”和“进位”合并到了一起。每次计算时先读一下低位的已有值，把新乘出来的积加进去，再把超过 10 的部分回归到高位，一步到位，代码干净，不容易漏进位。

2.2 竖式模拟：先逐位填入，最后统一进位

如果说卷积法是“边乘边进位”，那竖式模拟就是“先乘完，后整理”。思路更直观：先用一个数组把每一位的直接乘积都累加进去，最后从低位到高位统一处理一遍进位。

def multiply_v2(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): res[i + j + 1] += (ord(num1[i]) - 48) * (ord(num2[j]) - 48) carry = 0 for idx in range(m + n - 1, -1, -1): total = res[idx] + carry res[idx] = total % 10 carry = total // 10 start = 0 while start < m + n and res[start] == 0: start += 1 return ''.join(map(str, res[start:]))

这版代码更好理解：两层循环只做“乘法结果入座”，不管进位。等所有乘出来的数都放好了，再从数组末尾往前扫一遍，把超过 10 的部分一路往上送。最后carry理论上不会剩超过一位，因为res分配了m + n个位置，最坏情况下首位正好放进位。

我用 456 乘以 123 帮你走一遍逻辑：先算 6 乘 3 得 18，填到res[3]；再算 5 乘 3 得 15，填到res[2]；4 乘 3 得 12，填到res[1]。等所有位的乘积都填完，数组里的数可能都大于 9，最后统一进位后才会变成正常的多位数。

2.3 两种方案的对比与选型建议

我见过很多人在面试现场纠结用哪种，其实两者都能过，但风格不同：

我的建议是：平时练习两种都写一遍，面试时优先写你自己更有把握的那种。如果你对索引映射还不太熟，就用竖式模拟，逻辑直白，写错的概率低。等你想在简历上体现一点算法深度时，再聊聊卷积法的位置映射原理也不迟。

3. 代码实现与关键细节：多语言对照

3.1 Python 实现的常见细节

Python 版本里有个细节值得单独说：ord(num1[i]) - ord('0')和int(num1[i])效果相同，但前者是纯字符运算，效率更高，尤其在字符串长度很大的时候，能省掉不少字符解析的开销。

另外，res数组中的数字可能很大，Python 的列表没有类型限制，你不用担心里面的数超过某个范围。但在 C++ 和 Java 里，res数组里的数在累加时可能会超过int的范围吗？注意：因为每一个位置最多存 9 以内的最终结果，但中间累加过程可能会累计多位数字的乘积，所以在极端情况下，res[idx]确实可能超过 32767。稳妥的做法是使用long long或int（在 Java 里用int[]即可，因为单次累加的数理论上限大约 81 乘以位数，200 位的输入最多也就 16200，不会超 2 的 31 次方）。

3.2 Java 与 C++ 实现要点

Java 版本的核心代码逻辑和 Python 完全一致，但要注意字符转数字别写错：

class Solution { public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) return "0"; 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 mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); int p1 = i + j, p2 = i + j + 1; int total = mul + res[p2]; res[p1] += total / 10; res[p2] = total % 10; } } StringBuilder sb = new StringBuilder(); int start = 0; while (start < m + n && res[start] == 0) start++; for (int i = start; i < m + n; i++) sb.append(res[i]); return sb.length() == 0 ? "0" : sb.toString(); } }

注意 Java 的charAt返回是char，直接减'0'得到真正的数字值。C++ 则常写成num1[i] - '0'，逻辑一致。这类题目在 Java 中容易被坑的一个点是用Integer.parseInt去转换单个字符，其实完全没有必要，性能也不好。

3.3 边界条件与防御性编程清单

做字符串题，边界条件是最容易失分的地方。我总结了一份自查清单，每次写完代码按这个过一遍，基本能覆盖所有坑：

• num1 = "0"或num2 = "0"：直接返回"0"，否则前导零处理容易出bug。
• num1 = "1"或num2 = "1"：任何数乘 1 等于本身。
• 一位数乘一位数：比如"9" * "9" = "81"，验证结果位数是否符合预期。
• 结果本身是零的情况：比如大数乘零，确保输出是单个"0"而不是空串。
• 所有位置运算完之后，res数组中可能有多余的高位零，跳前导零的逻辑必须放在最后。

这些边界在 LeetCode 的测试用例中基本是标配，你只要漏一个，就会在提交时收到红色的 Wrong Answer。

4. 实战调试与高频 bug 实录

4.1 Bug 一：前导零没有去掉

这是出现频率最高的问题。很多人写完两层循环，直接就把res数组转成字符串返回，结果遇到"123"乘"456"的时候，输出可能变成"056088"之类的错误结果。

原因在于res数组分配了m + n位，但实际乘积可能只有m + n - 1位，最高位就是 0。如果不去掉它，输出就会多一个前导零。解决办法就是找到第一个非零的下标，从那里开始拼接。

这里有一个细节：如果全部是零，说明整个乘积就是 0，你需要在拼接前判断一下。如果你在函数开头已经做了“零值提前返回”，那这个兜底逻辑也可以留着当保险。

4.2 Bug 二：进位写反了位置

在卷积法里，res[p1] += total // 10和res[p2] = total % 10两行代码的左右顺序很容易搞混。我见过有人写成res[p1] = total // 10，把原来的高位值直接覆盖掉，结果一塌糊涂。

为什么会覆盖？因为res[p1]可能之前已经被别的乘法贡献过值了，你再把它整个替换掉，等于丢了前面的累加结果。正确做法是“加进”而不是“赋给”。同样的道理，res[p2]这边用的是赋值，因为它负责存本位的最终结果，之前的值已经通过total = mul + res[p2]合并进去了。

4.3 Bug 三：索引遍历顺序搞反

如果你从字符串的左边（最高位）开始遍历，也不是不行，但索引映射会变得非常绕。常见错误是，以为从左边开始就不用管位权偏移，结果低位和高位完全错位，输出结果差了好几个数量级。

我建议统一从右往左遍历，也就是range(m - 1, -1, -1)这种写法。这样num1[i]对应的位权就是10^(m - 1 - i)，实现竖式乘法时，索引关系非常清晰，不容易出错。

调试这类题，我有个习惯：先用测试用例"123" * "456"手跑一遍，确认中间过程的res数组每一步都符合预期，再提交。这个小习惯帮我省下了大量反复提交的时间。另外可以配合本地使用 Python 的int做结果校验，注意仅用于自测，提交代码里不能直接用。

4.4 自测用例：一份拿来即用的清单

我喜欢在本地准备一组固定用例，每次写完后跑一遍，基本能覆盖所有常见 bug：

每一条都有它在测试代码里的价值，特别是最后一条，Input 20 个 9 乘 20 个 9，专门用来验证你的代码不会溢出或者卡死。

5. 从字符串相乘延伸开去

5.1 大数四则运算体系

字符串相乘并不是孤立的一道题，它背后是一整套“大数运算”体系。字符串相加（415 题）、字符串相乘（43 题）、大数相减、大数相除，这些都是面试中常见的变体。

你会发现它们的底层思路高度一致：模拟人工计算过程，用数组存每一位，注意进位和借位，最后处理前导零。当你把字符串相乘写得滚瓜烂熟之后，再去做字符串相加就会觉得非常简单，因为那只是乘法的一层循环去掉一个维度而已。

大数加法有一个细节：从末尾逐位相加，维护carry，最后别忘了如果carry还等于 1，要在结果头部加一位。大数减法稍微复杂点，需要先比较两个数的大小，保证大减小，然后再按位借位。

5.2 性能优化与分治算法

字符串相乘的常规解法是O(m * n)的复杂度。如果输入的两个数字都有 10 万位，这个复杂度就是 100 亿次运算，严重超时。这时候就需要更高级的算法。

Karatsuba 算法是首个突破O(n^2)的大数乘法算法，复杂度为O(n^1.585)。它的核心思想是把两个大数各自拆成高低两段，然后利用高斯乘法技巧，用 3 次乘法替代 4 次乘法。更极端的场景会用快速傅里叶变换（FFT）把乘法复杂度降到O(n log n)，不过面试中基本不会考到这一步。

我的一位在量化公司做基础架构的朋友说，他们处理极其庞大的数据序列时，经常会用到这类优化的思想，虽然日常开发中未必真有人手写 FFT 乘法，但理解“用分治降低乘法次数”这种思路，对解决其他性能问题很有启发。

5.3 大数运算的实际应用场景

你可能会想：现在什么语言没有大数库？Python 的int本身就是无限精度，Java 有BigInteger，为什么还要学这个？

这是因为很多底层场景不能引入重量级依赖。比如一些早期的嵌入式系统、区块链代码、密码学库，或者某些对内存和性能要求极高的分布式系统模块，都需要自己实现大数运算。我自己参与过的一个老项目里，就因为引入第三方大数库导致整个包体积膨胀、构建时间变长，最后运维同事不得不把关键路径上的大数乘法改成手写版本，代码量其实不大，但运行效率和包体积明显改善。

另外，这类题目对工程化思维的训练价值很高：拆分问题、设计数据结构、处理边界、最后优化性能，这套流程在任何领域的开发里都通用。

6. 最后的建议与经验分享

我在实际刷题和面试别人的过程中，发现字符串相乘这道题最适合用来培养“手算思维”。很多人一遇到这种模拟类问题就慌，其实只要退一步想想“我自己在纸上会怎么算”，思路基本就打开了。我到现在还记得第一次在纸上画出 123 乘 45 的竖式，然后对照代码里p1、p2索引的那一刻，有种“原来代码就是数学”的顿悟感。

如果你正在准备面试，建议把这道题连同字符串相加（415）、字符串相加 II、大数减法一起练习。先把 Python 版写到默写级别，再用 Java 或 C++ 重写一遍，最后把边界用例跑熟。这个过程不用太久，但收获比光看题解大得多。

最后再分享一个小技巧：写完后别急着提交，先用上面那份自测清单跑一遍，特别是"99999999999999999999" * "99999999999999999999"这种超长用例。这比任何在线判题系统的反馈都更直观，因为你可以在本地打印中间数组，完完整整看到每一步进位是怎么发生的。等你把这道题彻底吃透，以后遇到任何“模拟手算”的题目，都会底气十足。