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

/*
wrong 1 (10/311 passed, 12 mins):
Line 34: Char 23: runtime error: signed integer overflow: 123456789 * 987654321 cannot be represented in type 'int' (solution.cpp)

think: 10^200: The maximum value that can be stored in an unsigned long long in C++ is 18,446,744,073,709,551,615. This is a 64-bit integer type, and it can hold values from 0 to (2^{64} - 1).
That's only 10^20!

have to do a deque of nums, and then do product in a elementary way. Do the computation in deque.

Runtime error: 
1. pad 0 to place + 1:
            while(result.size() <= place) { // insert 0 to bring result to place digits
                result.push_front(0);
            }
change "result.size() < place" to "result.size() <= place"
2. remove leading 0's in the string.

Wrong 2: (300/311 passed, 68 mins): num1 ="0",num2 ="0"
Output "", Expected "0"
Fix: handle 0 in num1 or num2:
        if(num2 == "0" || num1 == "0") {
            return "0";
        }
*/


class Solution {
public:
    void toNum(string s, deque<int>& dq) {
        for(auto const& ch : s) {
            int digit = ch - '0';
            dq.push_back(digit);
        }
    }

    // multiply deque * digit (single digit), and add multiplication number to result
    void helper(deque<int> const& dq, deque<int> & result, int digit, size_t place_in) {
        int carry = 0;
        size_t place = place_in;
        for(int i = dq.size() - 1; i >= 0; --i, place++) {
            // handle this digit
            int num = dq[i] * digit + carry;
            while(result.size() <= place) { // insert 0 to bring result to place digits
                result.push_front(0);
            }

            size_t result_pos = result.size() - 1 - place;
            num += result[result_pos];
            int front = num / 10;
            int residual = num % 10;
            result[result_pos] = residual;
            carry = front;
        }

        // now place is at the place of carry digit (i.e. the last ); continue to handle carry
        while(carry > 0) {
            while(result.size() <= place) { // insert 0 to bring result to place digits
                result.push_front(0);
            }
            size_t result_pos = result.size() - 1 - place;
            int num = carry + result[result_pos];
            int front = num / 10;
            int residual = num % 10;
            result[result_pos] = residual;
            carry = front;
            // next iter
            place++;
        }
    }

    string multiply(string num1, string num2) {
        // convert to num
        if(num1.size() < num2.size()) { // swap so that num2 has fewer digits
            swap(num1, num2);
        }
        if(num2 == "0" || num1 == "0") {
            return "0";
        }

        deque<int> dq1;
        toNum(num1, dq1);
        deque<int> dq2;
        toNum(num2, dq2);

        deque<int> result;
        // elementary multiplication
        size_t place = 0;
        for(int i = dq2.size() - 1; i >= 0; --i) {
            int digit2 = dq2[i];
            place = dq2.size() - 1 - i;
            if(digit2 == 0) { // multiplication == 0
                continue;
            }
            else {
                this->helper(dq1, result, digit2, place);
            }
        }
        // convert dq result to string
        string ret_str;
        for(auto const& digit: result) {
            ret_str += (char)('0' + digit);
        }

        // Remove leading zeros
        while (ret_str.size() > 1 && ret_str[0] == '0') { // Change 8: Remove leading zeros
            ret_str.erase(ret_str.begin());
        }
        return ret_str;
    }
};
10833