<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 addStrings(string num1, string num2) {
        int n = num1.size();
        int m = num2.size();
        
        if (n < m) {
            swap(num1, num2);
            swap(n, m);
        }

        num2 = string(n - m, '0') + num2;
        
        int carry = 0;
        string val = "";
        
        for (int i = n - 1; i >= 0; i--) {
            int sum = (num1[i] - '0') + (num2[i] - '0') + carry;
            carry = sum / 10;
            val += to_string(sum % 10);
        }

        if (carry) {
            val += to_string(carry);
        }
        
        reverse(val.begin(), val.end());
        return val;
    }

    string multiply(string num1, string num2) {
        int n = num1.size();
        int m = num2.size();
        
        vector<string> mul;
        string zeroPadding = "";

        for (int i = m - 1; i >= 0; i--) {
            string temp = zeroPadding;
            int carry = 0;

            for (int j = n - 1; j >= 0; j--) {
                int val = (num2[i] - '0') * (num1[j] - '0') + carry;
                carry = val / 10;
                temp += to_string(val % 10);
            }

            if (carry) {
                temp += to_string(carry);
            }

            reverse(temp.begin(), temp.end());
            mul.push_back(temp);

            zeroPadding += '0';
        }

        string result = "0";

        for (const string& num : mul) {
            result = addStrings(result, num);
        }

        int firstNonZero = 0;
        while (firstNonZero < result.size() && result[firstNonZero] == '0') {
            firstNonZero++;
        }

        result = result.substr(firstNonZero);

        return result.empty() ? "0" : result;
    }
};

18551