<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 solvem(string a, char b, int m, int ind){
        int carry = 0;
        int val = b-'0';
        string ans = "";
        for(int i=m-1;i>=0;i--){
            int tmp = (val*(a[i]-'0')) + carry;
            carry = tmp/10;
            ans = to_string(tmp%10)+ans;
        }
        if(carry!=0) ans = to_string(carry) + ans;
        while(ind>0){
            ans+="0";
            ind--;
        }
        cout<<ans<<endl;
        return ans;
    }
    string solvea(string a, string b){
        // a is cur, b is prev
        int n = a.size();
        int m = b.size();
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        string ans = "";
        int carry = 0;
        int i=0;
        for(i=0 ; i<m ;i++){
            int tmp = (b[i]-'0')+(a[i]-'0') + carry;
            carry = tmp/10;
            ans += to_string(tmp%10);
        }
        for(i=m; i<n; i++){
            int tmp = (a[i]-'0') + carry;
            carry = tmp/10;
            ans += to_string(tmp%10);
        }
        if(carry!=0) ans += to_string(carry);
        reverse(ans.begin(),ans.end());
        return ans;
    }
    string multiply(string num1, string num2) {
        int n = num1.size();
        int m = num2.size();
        string prev = solvem(num2,num1[n-1],m,0);
        for(int i=n-2;i>=0;i--){
            string cur = solvem(num2,num1[i],m,n-1-i);
            prev = solvea(cur,prev);
        }
        if(prev[0]=='0') return "0";
        return prev;
    }
};
32445