0043. Multiply Strings

1043. Multiply Strings

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
Note:

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 =="0") return "0";
        int size1 = num1.size(), size2 = num2.size();
        string str(size1+size2, '0'); //乘积最多有size1+size2位
        for(int i=size1-1; i>=0; i--){
            for(int j=size2-1; j>=0; j--){
                int pro = (num1[i] - '0') * (num2[j] - '0') + str[i+j+1] - '0'; // str[k]=num1[k]*num2[1]+num1[k-1]+num2[2]+……
                str[i+j+1] = pro % 10 + '0';
                str[i+j] += pro / 10;
            }
        }
        if(str[0] == '0') str = str.substr(1);
        return str;
    }
};