<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 mul(int x, string num1, int ct){
    int carry=0;
    string ans="";
    for(int i=0; i<num1.length(); i++){
        int rl=(num1[num1.length()-1-i]-'0')*x+carry;
        // cout<<rl<<endl;
        ans+=((rl%10)+48);
        carry=rl/10;
    }
    if(carry>0)ans+=carry+48;
    reverse(ans.begin(),ans.end());
    while(ct--)ans+='0';
    // cout<<ans<<endl;
    return ans;
}
string add(string s, string t){
    if(t.length()>s.length())return add(t,s);
    string ans="";
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    int carry=0;
    for(int i=0; i<t.length(); i++){
       int x=s[i]-'0'+t[i]-'0'+carry;
       ans+=(x%10)+48;
       carry=x/10;
    }
    for(int i=t.length(); i<s.length(); i++){
         int x=s[i]-'0'+carry;
       ans+=(x%10)+48;
       carry=x/10;
    }
    if(carry>0)ans.push_back(carry+48);
    reverse(ans.begin(),ans.end());
    return ans;
}
    string multiply(string num1, string num2) {
        if(num1.length()<num2.length())return multiply(num2,num1);
          int carry=0,ct=0;
          string ans="0";
          for(int i=0; i<num2.length(); i++){
            int x=num2[num2.length()-1-i]-'0';
           ans=add(ans,mul(x,num1,ct));
        //    cout<<ans<<endl;
           ct++;
          }
          reverse(ans.begin(),ans.end());
         for(int i=ans.size()-1; i>0; i--){
            if(ans[i]=='0')ans.pop_back();
            else break;
         }
              reverse(ans.begin(),ans.end());
          return ans;
    }
};
15773