<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:
    
    void addFromOffset(string& acc, int offset, const string& num)
    {
        int c=0;
        acc.resize(offset+num.size(), '0');
        
        for(int i=0; i<num.size(); i++)
        {
            int res = (num[i] - '0' + acc[offset+i] - '0') + c;
            int d = res %10;
            c = res / 10;
            
            acc[i+offset] = d +'0';
        }
        
        if(c>0)
        {
            acc.push_back(c + '0');
        }
    }
    
    string mulByDigit(const string& num, int digit)
    {
        int c=0;
        string result;
        result.resize(num.size(), '0');
        
        for(int i=0; i<num.size(); i++)
        {
            int res = ((num[i] - '0') * digit) + c;
            int d = res % 10;
            c = res / 10;
            
            result[i] = d + '0';
        }
        
        if(c>0)
        {
            result.push_back(c + '0');
        }
        
        return result;
    }
    
    string multiply(string num1, string num2) {
        
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        string result;
        for(int i=0; i<num1.size(); i++)
        {
            string res=mulByDigit(num2, num1[i] - '0');
            addFromOffset(result, i, res);
        }
        
        reverse(result.begin() ,result.end());
        result.erase(0, result.find_first_not_of('0'));
        if(result.empty())
            return string("0");
        
        return result;
    }
};
9906