<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:
    string addStrings(const string& str1, const string& str2) {
        auto num1it = str1.rbegin();
        auto num2it = str2.rbegin();

        string res = "";
        int digit1, digit2, sum;
        bool carry = false;
        while (num1it != str1.rend() && num2it != str2.rend()) {
            digit1 = (*num1it) - '0';
            digit2 = (*num2it) - '0';
            sum = digit1 + digit2 + carry;
            if (sum < 10) {
                res += ('0' + sum);
                carry = false;
            } else {
                res += ('0' + sum % 10);
                carry = true;
            }

            ++num1it;
            ++num2it;
        }

        while (num1it != str1.rend()) {
            sum = (*num1it) - '0' + carry;
            if (sum < 10)
                carry = false;
            res += ('0' + sum % 10);
            ++num1it;
        }

        while (num2it != str2.rend()) {
            sum = (*num2it) - '0' + carry;
            if (sum < 10)
                carry = false;
            res += ('0' + sum % 10);
            ++num2it;
        }

        if (carry)
            res += '1';

        reverse(res.begin(), res.end());
        return res;
    }

    string multStrings(const string& num, const int n) {
        string res = "";

        int carry = 0, mult;
        for (string::const_reverse_iterator numit = num.rbegin(); numit != num.rend(); ++numit) {
            mult = n * (*numit - '0') + carry;
            if (mult < 10) {
                res += ('0' + mult);
                carry = 0;
            } else {
                res += ('0' + mult % 10);
                carry = mult / 10;
            }
        }

        if (carry > 0)
            res += ('0' + carry);
        reverse(res.begin(), res.end());
        return res;
    }

public:
    string multiply(const string& num1, const string& num2) {
        if (num1 == "0" || num2 == "0")
            return "0";

        string res = multStrings(num1, num2.back() - '0');
        string shift = "0";
        for (string::const_reverse_iterator num2it = num2.rbegin() + 1; num2it != num2.rend(); ++num2it) {
            if (*num2it != '0')
                res = addStrings(res, multStrings(num1, *num2it - '0') + shift);
            shift += '0';
        }

        return res;
    }
};
12376