<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 intToString(unsigned long long n){
        string str="";
        while(n){
            char ch=n%10+'0';
            str+=ch;
            n=n/10;
        }
        reverse(str.begin(),str.end());
        return str;
    }
    string addStrings(string a, string b){
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int i=0,j=0;
        int carry=0;
        string finStr="";
        while(i<a.size() && j<b.size()){
            int sum=a[i]-'0'+b[j]-'0'+carry;
            finStr+=((sum%10)+'0');
            carry=sum/10;
            i++;
            j++;
        }
        while(i<a.size()){
            int sum=a[i]-'0'+carry;
            finStr+=((sum%10)+'0');
            carry=sum/10;
            i++;
        }
        while(j<b.size()){
            int sum=b[j]-'0'+carry;
            finStr+=((sum%10)+'0');
            carry=sum/10;
            j++;
        }
        if(carry!=0){
            finStr+=intToString(carry);
        }
        reverse(finStr.begin(),finStr.end());
        // cout<<finStr<<" ";
        return finStr;
    }
    string product(string s, int x){
        string prod="";
        reverse(s.begin(),s.end());
        int carry=0;
        for(int i=0; i<s.size(); ++i){
            int p=(s[i]-'0')*x+carry;
            prod+=(p%10+'0');
            carry=p/10;
            // cout<<prod<<" ";
        }
        if(carry!=0)prod+=intToString(carry);
        reverse(prod.begin(),prod.end());
        return prod;
    }
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0")return "0";
        vector<string> v;
        int n=num2.size();
        for(int i=0; i<n; ++i){
            string prod=product(num1,num2[i]-'0');
            // cout<<prod<<" ";
            for(int j=0; j<n-i-1; ++j)prod+='0';
            v.push_back(prod);
        }

        string ans=v[0];
        for(int i=1; i<v.size(); ++i){
            ans=addStrings(ans,v[i]);
        }
        return ans;
    }
};
18860