<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 s1 = num1.size(); int s2 = num2.size();
        vector<int> n1(s1); vector<int> n2(s2);

        for (int i = 0; i<s1; i++) {
            n1[i] = num1[i] - '0';
        }

        for (int i = 0; i<s2; i++) {
            n2[i] = num2[i] - '0';
        }

        vector<vector<int> > products(s2);
        for (int i = 0; i<s2; i++) {
            for (int j = 0; j<s1; j++) {
                products[i].push_back(n1[j] * n2[i]);
            }
        }

        for (int i = 0; i<s2; i++) {
            for (int j = s1-1; j>=1; j--){
                if (products[i][j] >= 10) {
                    products[i][j-1] += products[i][j]/10;
                    products[i][j] = products[i][j] % 10;
                }
            }
            
            if (products[i][0] >= 10) {
                auto it = products[i].begin();
                it = products[i].insert(it, products[i][0]/10);
                products[i][1] = products[i][1] % 10;
            }

            for (int j = 1; j<s2 - i; j++) {
                products[i].push_back(0);
            }
        }

        for (int i = 1; i<s2; i++) {
            int num = products[0].size() - products[i].size();
            for (int j = 0; j<num; j++) {
                auto it = products[i].begin();
                it = products[i].insert(it, 0);
            }
        }

        vector<int> ans;
        int carry = 0;
        for (int i = products[0].size()-1; i>=0; i--) {
            int amt = carry;
            for (int j = 0; j<products.size(); j++) {
                amt += products[j][i];
            }

            carry = (amt - (amt%10))/10;
            auto it = ans.begin();
            if (i != 0) it = ans.insert(it, amt%10);
            else it = ans.insert(it, amt);
        }

        string a = "";
        for (int i: ans) a += to_string(i);

        return a;
    }
};
21948