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

#define CTOI(x) int(x - '0')
#define ITOC(x) int(x + '0')

class Solution {
  std::string addStrings(std::string num1, std::string num2)
  {
    int carry = 0;
    int i1 = num1.length() - 1;
    int i2 = num2.length() - 1;
    std::string res;

    while (i1 >= 0 || i2 >= 0 || carry) {
      int x = carry;
      if (i1 >= 0) {
        x += CTOI(num1[i1]);
        i1--;
      }
      if (i2 >= 0) {
        x += CTOI(num2[i2]);
        i2--;
      }
      carry = x / 10;
      res.push_back(ITOC(x % 10));
    }
    std::reverse(res.begin(), res.end());

    return res;
  }

public:
  std::string multiply(std::string num1, std::string num2)
  {
    if (num1 == "0" || num2 == "0") return "0";
    if (num1.length() < num2.length()) std::swap(num1, num2);

    std::string res;
    std::string curr;
    int zeros = 1;
    int carry = 0;
    int i1 = num1.length() - 1;
    int i2 = num2.length() - 1;

    for (; i2 >= 0; i2--) {
      for (; i1 >= 0; i1--) {
        int x = CTOI(num1[i1]) * CTOI(num2[i2]) + carry;
        carry = x / 10;
        curr.insert(curr.begin(), ITOC(x % 10));
      }
      if (carry) {
        curr.insert(curr.begin(), ITOC(carry));
      }
      res = addStrings(res, curr);
      i1 = num1.length() - 1;
      curr.clear();
      curr.append(zeros++, '0');
      carry = 0;
    }

    return res;
  }
};
12068