43. Multiply Strings

这道题看了别人的程序，才对乘法有了更多的认识：

我们仍然是从低位到高位对每一位进行计算，假设第一个数长度是n，第二个数长度是m，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。对于某一位i，要计算这个位上的数字，我们需要对所有能组合出这一位结果的位进行乘法，即第1位和第i位，第2位和第i-1位，... ，然后累加起来，最后我们取个位上的数值，然后剩下的作为进位放到下一轮循环中。

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> d(m + n, 0);
        for(int i = 0; i < m; ++i){
            int a = num1[i] - '0';
            for(int j = 0; j < n; ++j){
                int b = num2[j] - '0';
                d[i + j] += a * b;
            }
        }
        string sb;
        for(int i = 0; i < d.size(); ++i){
            int digit = d[i] % 10;
            int carry = d[i] / 10;
            sb = to_string(digit) + sb;
            if(i < d.size() - 1){
                d[i + 1] += carry;
            }
        }
        while(sb.size() > 0 && sb[0] == '0'){
            sb.erase(sb.begin());
        }
        return sb.size() == 0 ? "0" : sb;
    }
};