题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

样例

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

说明

• num1 和 num2 的长度小于 110。
• num1 和 num2 只包含数字 0-9。
• num1 和 num2 均不以零开头，除非是数字 0 本身。
• 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

算法

(高精度乘法，模拟) $O(nm)$

1. 本题是经典的高精度乘法，可以直接模拟竖式乘法计算。
2. 乘积的最大长度为两个乘数的长度之和。

时间复杂度

• 设两个数字的位数分别是 $n$ 和 $m$，竖式乘法为两层循环错位相乘，故时间按复杂度是 $O(nm)$。

空间复杂度

• 需要额外 $O(nm)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.length(), m = num2.length();
        vector<int> a(n), b(m), c(n + m);

        for (int i = 0; i < n; i++)
            a[n - i - 1] = num1[i] - '0';

        for (int i = 0; i < m; i++)
            b[m - i - 1] = num2[i] - '0';

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                c[i + j] += a[i] * b[j];
                c[i + j + 1] += c[i + j] / 10;
                c[i + j] %= 10;
            }

        int l = n + m;
        while (l > 1 && c[l - 1] == 0) l--;

        string ans = "";
        for (int i = l - 1; i >= 0; i--)
            ans += c[i] + '0';

        return ans;
    }
};