<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 multiply(string num1, string num2) {
        if(num1=="0" || num2=="0")
            return "0";
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        string result;
        
        for(int i = 0; i<num2.size(); i++)
        {
            add(result, multiplyByDigit(num1, num2[i]-'0', i));
        }
        
        reverse(result.begin(), result.end());
        
        return result;
    }
    
    void add(string& num1, const string& num2)
    {
        num1.resize(max(num1.length(), num2.length()), '0');
        int carry = 0;
        for(int i = 0; i<num1.length(); i++)
        {
            int digit1 = num1[i] - '0';
            int digit2 = i<num2.length()?num2[i]-'0':0;
            int value = digit1+digit2+carry;
            num1[i] = value%10+'0';
            carry = value/10;
        }
        
        if(carry)
            num1.push_back(carry+'0');
    }
    
    string multiplyByDigit(const string& num, int digit, int zeros)
    {
        string result(zeros, '0');
        
        int carry = 0;
        for(char x : num)
        {
            int value = (x-'0')*digit+carry;
            result.push_back(value%10+'0');
            carry = value/10;
        }
        
        if(carry)
            result.push_back(carry+'0');
        
        return result;
    }
};
11141