43. 字符串相乘（字符串）

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1[0] == '0' || num2[0] == '0')
            return "0";
 
        int m = num1.size();
        int n = num2.size();
        //创建一个m+n长度的字符串，然后初始化为'0'
        string s(m + n, '0');
        for(int i = m - 1; i >= 0; --i)
        {
            for(int j = n - 1; j >= 0; --j)
            {
                int tmp = (num1[i] - '0') * (num2[j] - '0');
                tmp += s[i+j+1] - '0';
                s[i+j+1] = tmp%10 + '0';
                s[i+j] += tmp/10; 
            }
        }
        //防止高位为'0'，得截掉该小区间
        int index = 0;
        while(index < m+n && s[index] == '0')
            index++;
        return s.substr(index);
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size(), n2 = num2.size();
        string ret(n1 + n2, '0');
        for(int i = n1 - 1; i >= 0; --i)
        {
            int tmp = num1[i] - '0';
            for(int j = n2 - 1; j >= 0; --j)
            {
                int a = num2[j] - '0';                  // 每次选出来的乘数
                int mul = tmp*a + ret[i + j + 1] - '0'; // 计算出乘积和该位的总和
 
                ret[i + j] = (ret[i + j] - '0' + mul/10) + '0'; // 前一位加上进位
                ret[i + j + 1] = (mul%10) + '0';                // 该位变成余数
            }
        }
        for(int i = 0; i < ret.size(); ++i)
        {
            if(ret[i] != '0')
                return ret.substr(i);
        }
        return "0";
    }
};