<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, string num2) {
        int n1=num1.size(), n2=num2.size(), i, j;
        vector<int> A;
        for(i=0; i<n1; i++) {
            int a=num1[n1-1-i]-'0', c=0;
            vector<int> t;
            for(j=0; j<n2 || c; j++) {
                int b=(j<n2?num2[n2-1-j]-'0':0);
                int p=a*b+c;
                t.push_back(p%10);
                c=p/10;
            }
            for(j=0, c=0; j<t.size() || c; j++) {
                int k=i+j;
                if (A.size()==k) A.push_back(0);
                A[k]+=(j<t.size()?t[j]:0)+c;
                c=A[k]/10;
                A[k]%=10;
            }
        }
        while(A.size()>1 && A.back()==0) A.pop_back();
        string ret;
        for(i=A.size()-1; i>=0; i--) ret+=char('0'+A[i]);
        return ret;
    }
};
13303