<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(const string &s1, const string &s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        
        int i = n1 - 1, j = n2 - 1;
        int carry = 0;
        stack<int> ss;

        // Add both strings
        while (i >= 0 || j >= 0 || carry > 0) {
            int a1 = (i >= 0) ? s1[i] - '0' : 0;
            int a2 = (j >= 0) ? s2[j] - '0' : 0;
            
            int curr = a1 + a2 + carry;
            carry = curr / 10;
            curr %= 10;
            ss.push(curr);
            i--; j--;
        }

        string ans;
        while (!ss.empty()) {
            ans.push_back(ss.top() + '0');
            ss.pop();
        }

        return ans;
    }

    string singleMultiply(const string &s, int a) {
        int n = s.length();
        int i = n - 1;
        stack<int> ss;
        int carry = 0;

        while (i >= 0 || carry > 0) {
            int a1 = (i >= 0) ? s[i] - '0' : 0;
            int curr = a * a1 + carry;
            carry = curr / 10;
            curr %= 10;
            ss.push(curr);
            i--;
        }

        string ans;
        while (!ss.empty()) {
            ans.push_back(ss.top() + '0');
            ss.pop();
        }

        return ans;
    }

    string multiply(string s1, string s2) {
        if (s1 == "0" || s2 == "0") {
            return "0";
        }

        int n1 = s1.length();
        int n2 = s2.length();
        string ans = "0";

        for (int i = n1 - 1; i >= 0; --i) {
            int curr = s1[i] - '0';
            string temp = singleMultiply(s2, curr);
            
            // Append appropriate number of zeros (based on the current position)
            temp.append(n1 - 1 - i, '0');
            
            ans = add(ans, temp);
        }

        return ans;
    }
};

23800