<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>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    string addStrings(const string& num1, const string& num2) {
        int len1 = num1.size();
        int len2 = num2.size();
        string result;
        int carry = 0;
        int i = 0, j = 0;

        while (i < len1 || j < len2 || carry) {
            int digit1 = (i < len1) ? (num1[i] - '0') : 0;
            int digit2 = (j < len2) ? (num2[j] - '0') : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            result.push_back(sum % 10 + '0');
            i++;
            j++;
        }

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

public:
    string multiply(string num1, string num2) {
        int n1 = num1.size();
        int n2 = num2.size();
        vector<string> ans(n1 + n2,
                           "0"); // Result can be at most n1 + n2 digits

        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + stoi(ans[i + j + 1]); // Add previous carry

                ans[i + j + 1] = to_string(sum % 10);
                ans[i + j] = to_string(stoi(ans[i + j]) + (sum / 10));
            }
        }

        // Remove leading zeros
        string result;
        for (const auto& digit : ans) {
            if (!(result.empty() && digit == "0")) {
                result += digit;
            }
        }

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