<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) {
        if (num1=="0" || num2=="0") return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        //The maximum number of digits will be len1 + len2
        vector<int> digits;
        for (int i=0; i<len1+len2; i++) digits.push_back(0);

        int a;
        int b;
        int product;

        for (int i=len1-1; i>=0; i--) {
            for (int j=len2-1; j>=0; j--) {
                a = num1[i] - '0';
                b = num2[j] - '0';
                product = a*b;
                digits[i+j+1] += product%10;
                if (digits[i+j+1] >= 10) {
                    digits[i+j+1] = digits[i+j+1]%10;
                    digits[i+j] += 1;
                }
                digits[i+j] += product/10;
                if (digits[i+j] >= 10) {
                    digits[i+j] = digits[i+j]%10;
                    digits[i+j-1] += 1;
                }
            }
        }

        string s;
        for (int z: digits) s += to_string(z);
        if (s[0]=='0') s = s.substr(1,s.length()-1);
        return s;
    }
};
10215