<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 <string>
class Solution {
public:
    string multiply(string num1, string num2) {
        
        if(num1[0] == '0' || num2[0] == '0'){
            return "0";
        }
        string ans = "";
        vector <string> answer;
        int cnt = 0;

        for(int i=num1.size()-1; i>=0; i--)
        {
            string ans = "";
            int a = num1[i] - '0';
            int carry = 0;
            char sum;
            for(int j=num2.size()-1; j>=0; j--)
            {
                int b = num2[j] - '0';
                int product = a*b;

                sum = (product + carry)%10 + '0';
                carry = (product + carry)/10;
                ans.push_back(sum);
            }

            if(carry > 0){
                ans.push_back(carry + '0');
            }

            reverse(ans.begin(),ans.end());
            for(int k=0; k<cnt; k++)
            {
                ans.push_back('0');
            }

            cnt++;
            answer.push_back(ans);
        }

        int carry = 0;

        while(answer.size() > 0)
        {
            int sum = 0;
            int k = -1;
            for(int i=0; i<answer.size(); i++)
            {
                if(answer[i].size() > 0){

                    int j = answer[i][answer[i].size()-1] - '0';
                    answer[i].pop_back();
                    sum = sum + j;
                    if(answer[i].size() == 0){
                        k = i;
                    }
                }

                else{
                    k = i;
                }   
            }

            if(k >= 0){
                answer.erase(answer.begin()+k);
            }
            ans.push_back((sum%10 + carry)%10 + '0');
            carry = (sum+carry)/10;
        }

        if(carry > 0){
            ans.push_back(carry + '0');
        }

        reverse(ans.begin(),ans.end());
        int i=0;
        while(ans[i] == '0')
        {
            ans.erase(i,1);
        }
        return ans;
    }
};
12685