<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 {
    string multiply(const string& num, char ch, string& units) {
        unsigned int digit = ch - '0';
        if (digit == 0) {
            return "0";
        }
        
        string result = units;
        unsigned int carry = 0;
        for (int i = num.size() - 1; i >= 0; --i) {
            unsigned int d = num[i] - '0';
            unsigned int curr = (d == 0 ? 0 : d * digit) + carry;
            result.push_back((curr % 10) + '0');
            carry = curr / 10;
        }
        
        if (carry > 0) {
            result.push_back(carry + '0');
        }
        
        return result;
    }

    string multiplyInternal(const string& num1, const string& num2) {
        vector<string> products;
        string units;
        for (int j = num2.size() - 1; j >= 0; --j) {
            products.push_back(multiply(num1, num2[j], units));
            units.push_back('0');
        }
        
        string result;
        
        unsigned int place = 0;
        unsigned int carry = 0;
        while (true) {
            unsigned int sum = carry;
            bool done = true;
            for (int i = 0; i < products.size(); ++i) {
                if (place < products[i].size()) {
                    sum += products[i][place] - '0';
                    done = false;
                }
            }
            
            if (done) {
                break;
            }
            
            result.push_back((sum % 10) + '0');
            carry = sum / 10;
            place++;
        }
        
        if (carry)
            result += to_string(carry);
        
        reverse(result.begin(), result.end());
        
        return result;
    }

public:
    string multiply(string num1, string num2) {
        return num1.size() >= num2.size() ?
            multiplyInternal(num1, num2) : multiplyInternal(num2, num1);
    }
};
11450