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

<p><strong>Note:</strong>&nbsp;You must not use any built-in BigInteger library or convert the inputs to integer directly.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> num1 = "2", num2 = "3"
<strong>Output:</strong> "6"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> num1 = "123", num2 = "456"
<strong>Output:</strong> "56088"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num1.length, num2.length &lt;= 200</code></li>
	<li><code>num1</code> and <code>num2</code> consist of digits only.</li>
	<li>Both <code>num1</code> and <code>num2</code>&nbsp;do not contain any leading zero, except the number <code>0</code> itself.</li>
</ul>

class Solution {
public:
    string sum(vector<vector<int>>&res){
        vector<int>ans=res.back();
        res.pop_back();
        vector<int>cur;
        for(auto it:res){
            cur.clear();
            int carry=0;
            for(int i=0;i<ans.size() || i<it.size();i++){
                int dig1= (i<it.size())?it[i]:0;
                int dig2=(i<ans.size())?ans[i]:0;
                int sumNum=dig1+dig2+carry;
                cur.push_back(sumNum%10);
                carry=sumNum/10;
            }
            if(carry){
                cur.push_back(carry);
            }
            ans=cur;
        }
        string ansStr="";
        for(auto it:ans){
            ansStr+=to_string(it);
        }
        return ansStr;
    }
    vector<int>multiply(string num,char x,int idx){
        vector<int>res(idx,0);
        int carry=0;
        int sum=0;
        for(auto it:num){
            int pro=(it-'0')*(x-'0')+carry;
            carry=pro/10;
            res.push_back(pro%10);
        }
        if(carry){
            res.push_back(carry);
        }
        return res;
    }
    string multiply(string n1, string n2) {
        if(n1=="0" || n2=="0")return "0";
        reverse(n1.begin(),n1.end());
        reverse(n2.begin(),n2.end());
        vector<vector<int>>res;
        for(int i=0;i<n2.length();i++){
            res.push_back(multiply(n1,n2[i],i));
        }
        string ans=sum(res);
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
21639