<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>

#define pb push_back
class Solution {
public:
    void add(string s1, string &s2) {
        int i=0,n1=s1.length(),n2=s2.length(),carry=0;
        while(i<n1 && i<n2) {
            int val = (s1[i]-'0') + (s2[i]-'0') + carry;
            s2[i] = (val%10)+'0';
            carry = val/10;
            i++;
        }
        while(i<n2) {
            int val = (s2[i]-'0') + carry;
            s2[i] = (val%10)+'0';
            carry = val/10;
            i++;
        }
        while(i<n1) {
            int val = (s1[i]-'0') + carry;
            s2 += (val%10)+'0';
            carry = val/10;
            i++;
        }
        if(carry)
            s2 += (carry+'0');
    }

    string multiply(string num1, string num2) {
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        string res;

        int pos=0;
        for(char c: num1) {
            int val = c-'0', carry=0;
            string str;
            for(int i=0;i<pos;i++)
                str+='0';

            for(int i=0;i<num2.size();i++) {
                int val2 = num2[i]-'0';
                int sum = (val*val2 + carry)%10;
                carry = (val*val2 + carry)/10;
                str += (sum+'0');
            }
            if(carry)
                str += (carry+'0');
            add(str,res);
            pos++;
        }
        for(int i=res.size()-1;i>=0;i--) {
            if(i==0)
                break;
            if(res[i]=='0')
                res.pop_back();
            else break;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
11759