LeetCode 43. 字符串相乘

◎

本节目标

把每对数字的乘积累加到长度为 m + n 的数组，并从低位向高位处理进位。

这道题延续解析与大整数的逐位算术模板：不构造每一行中间字符串，而是把所有数字对的贡献累加到固定长度数组。

查看原题

题意与约束

给定两个非负十进制整数字符串，不能直接使用大整数库，返回两数的乘积。任意一个输入为 0 时，结果必须是单个字符 0。

定位每一对数字

长度为 m 和 n 的两个数相乘，结果最多有 m + n 位。若两个数字的下标分别为 i 和 j，其乘积应先累加到数组位置 i + j + 1；该位置产生的进位再加到前一位 i + j。

跳过前导零

数组前端可能保留零，例如 123 × 456 的数组长度为六但答案只有五位。完成全部累加后跳过前导零；提前特判零输入可以避免得到空字符串。

代码实现

C++

C++17

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        int firstSize = static_cast<int>(num1.size());
        int secondSize = static_cast<int>(num2.size());
        vector<int> digits(firstSize + secondSize);

        for (int firstIndex = firstSize - 1; firstIndex >= 0; firstIndex--) {
            for (int secondIndex = secondSize - 1; secondIndex >= 0; secondIndex--) {
                int product = (num1[firstIndex] - '0') * (num2[secondIndex] - '0');
                int position = firstIndex + secondIndex + 1;
                int sum = digits[position] + product;
                digits[position] = sum % 10;
                digits[position - 1] += sum / 10;
            }
        }

        string result;
        int index = 0;
        while (index < static_cast<int>(digits.size()) && digits[index] == 0) {
            index++;
        }
        while (index < static_cast<int>(digits.size())) {
            result.push_back(static_cast<char>('0' + digits[index]));
            index++;
        }

        return result;
    }
};

Python

Python 3

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'

        digits = [0] * (len(num1) + len(num2))
        for first_index in range(len(num1) - 1, -1, -1):
            for second_index in range(len(num2) - 1, -1, -1):
                product = int(num1[first_index]) * int(num2[second_index])
                position = first_index + second_index + 1
                total = digits[position] + product
                digits[position] = total % 10
                digits[position - 1] += total // 10

        index = 0
        while digits[index] == 0:
            index += 1
        return ''.join(str(digit) for digit in digits[index:])

复杂度分析

设两个字符串长度为 m 和 n，时间复杂度为 O(m * n)，额外空间复杂度为 O(m + n)。

易错点

• 结果数组开成 m + n - 1，遗漏最高位进位。
• 把乘积位置写成 i + j，使所有数字错位一位。
• 忘记跳过前导零，或零输入时返回空串。

模式迁移

长整数的乘法、进制转换中的逐位累加都可先固定每个局部贡献的位置，再按进位规则归并；若需要更高性能，再学习分治乘法。