43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

S: math O(mn)

长度为n1,n2的两数相乘，结果是长为n1 + n2的数(可能开头有0). num1[i]和num2[j]相乘的结果会在第i+j+1位，进位在i+j位

    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> num(n1 + n2);
        string result = "";
        for (int i = n1 - 1; i >= 0; --i) {  //从后往前容易处理进位
            for (int j = n2 - 1; j >= 0; --j) {
                int sum = (num1[i] - '0') * (num2[j] - '0') + num[i + j + 1]; //要加上原有的值一起处理
                num[i + j + 1] = sum % 10;
                num[i + j] += sum / 10;
            }
        }
        for (int i : num) {
            if (!(i == 0 && result.size() == 0)) { //去除开头的‘0’
                result += to_string(i);
            }
        }
        return result.size() == 0? "0" : result;
    }