[Lc]43字符串相乘

题目

题解

• 时间复杂度$O(mn)$
• 空间复杂度$O(m+n)$

class Solution {
public:
    string multiply(string num1, string num2) {
        string res = "";//初始化结果res
        int len1 = num1.size(), len2 = num2.size();
        //初始化两字符串的长度用于后续创建数组
        vector<int> vals(len1+len2);//创建数组
        for(int i = len1-1; i>=0; i--){
            for(int j = len2-1; j>=0; j--){//两个循环把每一位的数相乘
                int mul = (num1[i]-'0') * (num2[j]-'0');//计算这一位的乘法结果
                int p1 = i+j, p2 = i+j+1, sum = mul + vals[p2];//高位p1,低位p2，sum是乘法结果加上原来乘法在低位的进位
                vals[p1] += sum/10;//大于10的部分存在高位
                vals[p2] = sum%10;//小于10的地方存在低位
            }
        }
        for(int val : vals){//每一位转int到string
            if(res.empty() && val == 0) continue;//若是首位且是0则不转换（全0变为空，因此return部分要修改）
            res += '0'+val;
        }
        return res.empty()? "0" : res;//若全空则返回0，否则返回结果
    }
};