<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, char c){
        string s;
        num1 = '0' +num1;
        int carry = 0, n = num1.size();
        for(int i = n-1;i>=0;i--){
            int val = (c-'0') * (num1[i]-'0') + carry;
            s += val%10 + '0';
            carry = val/10;
        }
        while(s.back() == '0' and s.size() > 1)
            s.pop_back();
        reverse(s.begin(),s.end());
        return s;
    }

    string add(string &num1, string &num2) {
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        string s;
        int carry = 0, n = max(num1.size(),num2.size());
        for(int i = 0;i<=n;i++){
            int val = carry;
            if(i < num1.size())
                 val += (num1[i]-'0');
            if(i < num2.size())
                 val += (num2[i]-'0');

            s += val%10 + '0';
            carry = val/10;
        }
        while(s.back() == '0' and s.size() > 1)
            s.pop_back();
        reverse(s.begin(),s.end());
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        return s;
    }

    string multiply(string num1, string num2) {
        string ans;
        if(num1.size()<num2.size())
            return multiply(num2,num1);
        reverse(num2.begin(),num2.end());
        for(char c : num2){
            // cout << '#' << num1 << ' ' << c <<endl;
            string x = multiply(num1,c);
            // cout << x << ' ' << x.size() << endl;
            ans = add(ans,x);
            num1 += '0';
        }
        return ans;
    }
};
15464