<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>

/*
 5
017
428
  6
*/


class Solution {
public:
    string multiply(const string& num1, const string& num2) {
        const string*  p1 = &num1;
        const string*  p2 = &num2;
        if(num1.size() < num2.size()){
            p1 = &num2;
            p2 = &num1;
        }
        if(*p2 == "0"){
            return "0";
        }

        deque<char>res;


        for(auto it2 = p2->rbegin(); it2 < p2->rend(); ++it2){ // bottom number
            uint8_t carry = 0;

            deque<char> temp(distance(p2->rbegin(), it2), '0');
            char d2 = *it2;
            for(auto it1 = p1->rbegin(); it1 < p1->rend(); ++it1){
                char d1 = *it1;
                uint8_t n = (d1-'0')*(d2-'0')+carry;
                temp.push_front(static_cast<char>(n%10 + '0'));
                carry = n/10;
            }
            if(carry > 0){
                temp.push_front(static_cast<char>(carry+'0'));
            }
            // std::cout << res << '+' << temp << '=';
            res = add(res, temp);
            // std::cout << res << std::endl;
        }

        return string(res.begin(), res.end());
    }

private:
    deque<char> add(const deque<char>& small, const deque<char>& big){
        uint8_t carry = 0;
        int i = 0;
        deque<char> res;
        while(i < big.size()){
            char dbig = big[big.size()-i-1];
            char dsmall = '0';
            if(i < small.size()){
                dsmall = small[small.size()-i-1];
            }
            uint8_t n = (dbig-'0')+(dsmall-'0') + carry;
            res.push_front(static_cast<char>(n%10+'0'));
            carry = n/10;
            ++i;
        }
        if(carry > 0){
            res.push_front(static_cast<char>(carry+'0'));
        }
        
        return res;
    }
};
23491