<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 {
private:
    int atoi(char c){
        return c-'0';
    }

    string add(string a, string b){
        string ans = "";
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = a.size(), m = b.size();

        int carry=0, i=0;
        for(i=0;i<min(n,m);i++){
            int x = atoi(a[i]) + atoi(b[i]) + carry;
            ans += to_string(x%10);
            carry = x/10;
        }
        while(i<n){
            int x = atoi(a[i])+carry;
            ans += to_string(x%10);
            carry = x/10;
            i++;
        }
        while(i<m){
            int x = atoi(b[i])+carry;
            ans += to_string(x%10);
            carry = x/10;
            i++;
        }

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

        reverse(ans.begin(), ans.end());
        return ans;
    }

    string singleDigitMultiply(char c, string s){
        string ans = "";
        reverse(s.begin(), s.end());

        int n = s.length();
        int carry = 0;
        int num = atoi(c);
        for(int i=0;i<n;i++){
            int x = num*atoi(s[i])+carry;
            ans += to_string(x%10);
            carry = x/10;
        }

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

        reverse(ans.begin(), ans.end());
        return ans;
    }

public:
    string multiply(string num1, string num2) {
        // singleDigitMultiply()
        // add()

        string ans = "";
        for(int i=num1.size()-1;i>=0;i--){
            string temp = singleDigitMultiply(num1[i], num2) + string(num1.size()-1-i, '0');
            // cout<<temp<<endl;
            ans = add(ans, temp);
        }

        while(ans.size()>1 && ans[0]=='0') ans = ans.substr(1);

        return ans;

    }
};
17316