<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 add(string s1, string s2){
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int idx = 0;
        int carry = 0;
        string res = "";
        while(idx < min(s1.size(), s2.size())){
            int x = s1[idx] - '0';
            int y = s2[idx] - '0';
            int digit = (x + y + carry) % 10;
            carry = (x + y + carry) / 10;
            res += '0' + digit;
            idx++;
        }
        while(idx < s1.size()){
            int digit = s1[idx] - '0' + carry;
            carry = digit / 10;
            digit = digit % 10;
            res += '0' + digit;
            idx++;
        }
        while(idx < s2.size()){
            int digit = s2[idx] - '0' + carry;
            carry = digit / 10;
            digit = digit % 10;
            res += '0' + digit;
            idx++;
        }

        if(carry) res += '0' + carry;

        reverse(res.begin(), res.end());
        return res;
    }
    string multiply(string num1, string num2) {
        string res = "0";
        if(num1.size() < num2.size()) swap(num1, num2);
        for(int i=num2.size()-1, j=0; i>=0; i--, j++){
            string temp = "0";
            for(int k=0; k<int(num2[i]-'0'); k++) temp = add(num1, temp);
            for(int k=0; k<j; k++) temp += '0';
            res = add(res, temp);
        }
        return res;
    }
};
20713