<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 {
private:
    void update(string& res, const string& num1, int digit, int d)
    {
        if(!digit)
        {
            return;
        }
        int i = num1.size() - 1;
        string added = "";
        int cur = 0;
        while(i >= 0 || cur)
        {
            if(i >= 0)
            {
                cur += (num1[i--] - '0') * digit;
            }
            added += cur % 10 + '0';
            cur /= 10;
        }
        cur = 0;
        i = 0;
        while(i < added.size() || cur)
        {
            cur += res[d] - '0';
            if(i < added.size())
            {
                cur += added[i++] - '0';
            }
            res[d++] = cur % 10 + '0';
            cur /= 10;
        }
    }
public:
    string multiply(string num1, string num2)
    {
        string res = string(num1.size() + num2.size(), '0');
        for(int i = num2.size() - 1, d = 0; i >= 0; i--, d++)
        {
            update(res, num1, num2[i] - '0', d);
        }
        while(res.size() > 1 && res.back() == '0')
        {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
11141