Multiply Strings

43. 字符串相乘

分析

倒序存储数字
- 将 num1 和 num2 中的每一位字符转为整数，并倒序存入数组 A 和 B 。这样可以方便从低位开始模拟乘法
模拟乘法逐位累加
- 两个长度分别为 n 和 m 的数字相乘，结果最多有 n + m 位
- 使用两个倒序数组 A 和 B ，逐位计算乘积，并将结果累加到结果数组 C 中：
  - 对于 A[i] * B[j] ，结果累加到 C[i + j]
处理进位
- 遍历结果数组 C ，将每位上的数处理为个位，进位部分加到下一位
移除前导零并生成结果字符串
- 从结果数组的高位向低位查找第一个非零位，忽略高位多余的零
- 将结果数组转为字符串输出

时间复杂度

两个数字的长度分别为 n 和 m
遍历两者进行乘法计算，需要 O(n * m)
进位处理和结果拼接的时间为 O(n + m)

总体时间复杂度为 O(n * m)

空间复杂度

结果数组 C 的长度为 n + m

空间复杂度为 O(n + m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution {
public:
    string multiply(string num1, string num2)
    {
        // 获取两个字符串的长度
        int n = num1.size(), m = num2.size();

        // 将 num1 和 num2 转换为倒序数组 A 和 B
        std::vector<int> A, B;
        for (int i = n - 1; i >= 0; --i)
            A.push_back(num1[i] - '0');
        for (int i = m - 1; i >= 0; --i)
            B.push_back(num2[i] - '0');

        // 初始化结果数组 C，最大长度为 n + m
        std::vector<int> C(n + m, 0);

        // 模拟乘法逐位累加
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                C[i + j] += A[i] * B[j];

        // 处理进位
        for (int i = 0, t = 0; i < C.size(); ++i)
        {
            t += C[i];
            C[i] = t % 10;  // 当前位保留个位
            t /= 10;        // 进位部分
        }

        // 移除高位多余的零
        int k = C.size() - 1;
        while (k > 0 && C[k] == 0) --k;

        // 将结果数组转换为字符串
        std::string res;
        while (k >= 0)
            res += C[k--] + '0';

        return res;
    }
};