<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 multiply(string num1, string num2) {

        if(num1 == "0" || num2 == "0") return "0";

        int n1 = num1.size();
        int n2 = num2.size();

        map<int, vector<int>> m1;
        int base = -1;

        for(int i=n2-1;i>=0;i--) {
            int carry = 0;
            int position = 0;
            base++;
            for(int j=n1-1;j>=0;j--) {
                int d2 = num2[i] - '0';
                int d1 = num1[j] - '0';

                int curr = (d1*d2) + carry;
                m1[base + position++].push_back(curr%10);
                carry = curr/10;
            }
        
            if(carry != 0) m1[base + position].push_back(carry);
        }

        string res = "";
        int carry = 0;
        for(auto p : m1) {
            vector<int> bruv = p.second;
            int check = 0;
            
            for(auto h : bruv) {
                check += h;
            }
            check += carry;
            res += to_string(check%10);
            carry = check/10; 
        }

        if(carry != 0) res += to_string(carry);

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

        return res; 
    }
};
22256