<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_a_number(string s, int num){
        if(num ==0) return "0";
        int carry  = 0;
        string ans = "";
        for(int i =0; i < s.size(); ++i){
            int idx = s.size() - 1 -i;
            int n = (s[idx] - '0') * num + carry;
            ans += to_string(n%10);
            carry = n/10;
        }
        if(carry)
            ans += to_string(carry);
        reverse(ans.begin(), ans.end());
        return ans;
    }

    string add_two_numbers(string s1, int end1, string s2){
        if(s1.size() ==0) return s2;
        string ans;
        int n1 = s1.size();
        if(end1 > n1-1)
            return s2 + s1;
        int carry = 0;
        int j = s2.size() -1;
        int i =0 ;
        for(i = n1 - 1 - end1; i >=0; --i){
            int n = (s1[i] -'0') + (s2[j]-'0') + carry;
            ans += to_string(n%10);
            carry = n/10;
            --j;
            if(j <0) break;
        }
        while(j >= 0){
            int n = (s2[j] - '0') + carry;
            ans += to_string(n%10);
            carry = n/10;
            --j;
        }
        if(carry)
            ans += '1';
        reverse(ans.begin(), ans.end());
        if(i > 0){
            ans = s1.substr(0, i) + ans;
        }
        ans += s1.substr(n1-end1);
        return ans;
    }

    string multiply(string num1, string num2) {        
        // cout << multiply_a_number("9", 9) << endl;
        // cout << add_two_numbers("533789", 0,  "0") << endl;
        string ans = "";
        for(int i = 0; i < num2.size(); ++i){
            int idx = num2.size() - 1 - i;
            int n = num2[idx] - '0';
            string mul_res = multiply_a_number(num1, n);
            ans = add_two_numbers(ans, i, mul_res);
        }
        while(ans[0] == '0' && ans.size() > 1){
            ans.erase(0, 1);
        }
        return ans;
    }
};
16081