<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.size()+num2.size()<18){
            return to_string(stoll(num1)*stoll(num2));
        }
        //split the num1 and num2;
        //num1 and num2 should have the same digit length
        //M=(a+b)(c+d)
        //ac+bd = M-ac-bd
        if(num1.size()<num2.size()){
            return multiply(num2,num1);
        }
        int n = num1.size();
        string a = num1.substr(0,n/2);
        string b = num1.substr(n/2,n-n/2);
        string zeros(n-n/2,'0');
        auto aterm = multiply(a,num2)+zeros;
        //cout<<"aterm:"<<aterm<<endl;
        auto bterm = multiply(b,num2);
        //cout<<bterm<<endl;
        return bigAdd(aterm,bterm);

    }
    string bigAdd(string num1,string num2){
        if(max(num1.size(),num2.size())<18){
            return to_string(stoll(num1)+stoll(num2));
        }
        if(num1.size()>num2.size()){
            return bigAdd(num2,num1);
        }
        //pad zeros
        string zeros(num2.size()-num1.size(),'0');
        num1 = zeros+num1;
        int n = num2.size();
        int carry = 0;
        for(int i=n-1; i>=0;i--){
            num2[i]=num1[i]+num2[i]+carry-'0';
            carry=0;
            if(num2[i]>'9'){
                num2[i]-=10;
                carry=1;
            }
        //121876543211400000
        //000056087901235269
       //1232933631112635269
        }
        if(carry==1){
            return "1"+num2;
        }
        return num2;
    }
};
21330