题目重点：LC43 的十进制字符串乘法，用 m+n 位数组对齐乘积并处理进位、零和前导零，分析 O(mn) 时间。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入是非空 ASCII 十进制数字串，允许前导零；输出规范化为无前导零的非负十进制串。
- 只允许单个字符转 0..9 参与乘法，不把整体操作数转大整数；不处理符号或小数。
解题路线
- 先去掉前导零；任一数为 0 时直接返回 '0'。分配长度 m+n 的整型数组，足够存两个 m/n 位数的乘积。
- 从右向左遍历两串；位 a[i]×b[j] 的个位累加到 result[i+j+1]，十位进到 result[i+j]。
- 内层循环从低位到高位，前一轮留在 result[i+j] 的进位会在后续以该位置作为低位时继续归一；所有数位最终在 0..9。
- 去掉结果数组前导零并拼字符串。用 123×45 逐项检验对齐：3×5 落最右位，2×4 的十位落更左一位。
手动走一遍
'00123'×'045' 先规范化为 123×45，竖式得到 5535。'0'×任何输入应直接返回 '0'；'99'×'99'=9801，检验连续进位。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def multiply_strings(a: str, b: str) -> str:
"""Multiply nonnegative decimal strings without converting whole operands to int."""
if not a or not b or any(c < '0' or c > '9' for c in a + b):
raise ValueError('expected nonnegative decimal strings')
a, b = a.lstrip('0') or '0', b.lstrip('0') or '0'
if a == '0' or b == '0':
return '0'
m, n = len(a), len(b)
result = [0] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
product = (ord(a[i]) - 48) * (ord(b[j]) - 48) + result[i + j + 1]
result[i + j + 1] = product % 10
result[i + j] += product // 10
return ''.join(map(str, result)).lstrip('0')
if __name__ == '__main__':
assert multiply_strings('00123', '045') == '5535'
复杂度
O(mn) 次单数字相乘、O(m+n) 结果数组空间；去零与拼接 O(m+n)。固定宽度语言的每个乘积 9×9 加当前位仍在小整数范围。
易错点与追问
容易失分的边界
- 偷偷把整个字符串转 BigInteger，违反题目明确约束。
- 结果数组只开 max(m,n) 位，乘积可能有 m+n 位。
- carry 位置用 i+j+1 而不是 i+j，导致对齐错一位。
- 保留 0000 或输出空串而非 '0'。
继续深挖
- 若输入非常长，Karatsuba 或 FFT 何时值得用？
- 若允许负号，如何处理符号和零归一化？
- 如何在不生成全部字符串前逐段输出乘积？
