1.题目描述

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

示例 2:

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

2.思路

（1）乘数 num1 位数为 M，被乘数 num2 位数为 N，则 num1 x num2 结果 res 最大总位数为 M+N
（2）num1[i] x num2[j] 的结果为 num(位数为两位，“0x”,"xy"的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]，如下图所示。

3.代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0"){
            return "0";
        }
        vector<int> res_vec(num1.size() + num2.size());
        for(int i = num1.size() - 1; i >= 0; --i){
            int n1 = num1[i] - '0';
            for(int j = num2.size() - 1; j >= 0; --j){
                int n2 = num2[j] - '0';
                int num = res_vec[i + j + 1] + n1 * n2;
                res_vec[i + j + 1] = num % 10;
                res_vec[i + j] += num / 10;
            }
        }
        string res = "";
        for(int i = 0; i < res_vec.size(); ++i){
            if(i == 0 && res_vec[i] == 0){
                continue;
            }
            res += to_string(res_vec[i]);
        }

        return res;
    }
};

4.复杂度分析

时间复杂度：O(MN)
空间复杂度：O(M+N)