题目描述

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

样例

示例 1:
输入: num1 = "2", num2 = "3"

输出: "6"
示例 2:

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

算法1

(高精度乘法) $O(nm)$

使用字符串来模拟小学竖式。

时间复杂度

两重循环，所以是$O(nm)$

参考文献

C++ 代码

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();

        string res(m + n + 1, '0');
        for (int j = 0; j < n; ++j){
            for (int i = 0; i < m; ++i){
                int num = (res[i + j] - '0') + (num1[m - 1 - i] - '0') * (num2[n - 1 - j] - '0');
                res[i + j] = num % 10 + '0';
                res[i + j + 1] += num / 10;
            }
        }

        while (res.size() && res.back() == '0') res.pop_back();
        return res.empty() ? "0" : string(res.rbegin(), res.rend());
    }
};