[数据结构与算法]Leetcode 43. 字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1= num1.size(), n2 = num2.size();
        string ret(n1 + n2, '0');
        int start = 0;
        for(int j = n2 - 1; j >= 0; --j){
            int k = start;
            int carry = 0;
            for(int i = n1-1; i >= 0; --i){
              int sum = (num2[j] - '0') * (num1[i] - '0') + carry + (ret[k] - '0');
            carry = sum/10;
            ret[k] = (sum % 10 + '0');
            ++k;
            }
            if(carry){
                ret[k] = carry + '0';
            }
            ++start;
         
        }
        int k = n1 + n2 - 1;
        while(k >= 0 && ret[k] == '0'){
            --k;
        }
        if(k == -1)
        return "0";

        ret.erase(ret.begin() + k + 1, ret.end());
        reverse(ret.begin(), ret.end());
        return ret;
    }
};