<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 multiply(string num1, string num2) {
        int n=num1.size();
        int m=num2.size();
        if(num1=="0"||num2=="0") return "0";
        vector<vector<int>> v(m);
        int ct=0;
        for(int i=0;i<m;i++){
           for(int k=0;k<ct;k++) v[i].push_back(0);
            int f=0;
            for(int j=n-1;j>=0;j--){
                int a=num1[j]-'0';
                int b=num2[m-i-1]-'0';
                // cout<<a<<" "<<b<<"\n";
                int c=a*b;
                c+=f;
                int x=c/10;
                int y=c%10;
                f=x;
                v[i].push_back(y);
            }
            while(f!=0){
                v[i].push_back(f%10);
                f/=10;
            }
            ct++;
        }
        int mx=v[m-1].size();
        for(auto &it:v){
            while(it.size()<mx){
                it.push_back(0);
            }
            reverse(it.begin(),it.end());
        }
        vector<int> ans;
        int f=0;
        for(int i=mx-1;i>=0;i--){
            int c=0;
            for(int j=0;j<m;j++){
                c+=v[j][i];
            }
            c+=f;
            int a=c%10;
            int b=c/10;
            ans.push_back(a);
            f=b;
        }
        while(f!=0){
            ans.push_back(f%10);
            f/=10;
        }
        reverse(ans.begin(),ans.end());
        string fans="";
        for(auto it:ans){
            fans+=(char)('0'+it);
        }
        return fans;
    }
};
19786