<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 add(string num1, string num2) {
        int sum = 0, carry = 0, curr = 0;
        string res = "";
        int len1 = num1.length(), len2 = num2.length();
        while (len1 - 1 - curr >= 0 && len2 - 1 - curr >= 0) {
            int dig1 = int(num1[len1 - 1 - curr]) - 48,
                dig2 = int(num2[len2 - 1 - curr]) - 48;
            sum = dig1 + dig2 + carry;
            carry = sum / 10;
            sum = sum % 10;
            res.insert(0, to_string(sum));
            curr++;
        }
        while (len1 - 1 - curr >= 0) {
            int dig1 = int(num1[len1 - 1 - curr]) - 48;
            sum = dig1 + carry;
            carry = sum / 10;
            sum = sum % 10;
            res.insert(0, to_string(sum));
            curr++;
        }
        while (len2 - 1 - curr >= 0) {
            int dig1 = int(num2[len2 - 1 - curr]) - 48;
            sum = dig1 + carry;
            carry = sum / 10;
            sum = sum % 10;
            res.insert(0, to_string(sum));
            curr++;
        }
        if (carry > 0)
            res.insert(0, to_string(carry));
        return res;
    }

    string multiply(string num1, string num2) {
        int len2 = num2.length(), count = 0;
        string res = "0";
        for (int i = len2 - 1; i >= 0; --i) {
            int num = int(num2[i]) - 48;
            string value = "0";
            for (int j = 1; j <= num; ++j) {
                value = add(value, num1);
            }
            for (int j = i; j < len2 - 1; ++j) {
                value += "0";
            }
            res = add(res, value);
        }

        while (res[count] == '0' && count < res.length() - 1) {
            if (res[count + 1] == '0')
                res.erase(count, 1);
            else
                count++;
        }
        return res;
    }
};
22565