<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 reverse(string str)
    {
        string result = "";
        int strSize = str.size();
        for(int i = strSize - 1; i >= 0; i--)
        {
            result += str[i];
        }
        return result;
    }

    string sumStrings(string s1, string s2)
    {
        int length1 = s1.size();
        int length2 = s2.size();
        string result;
        int one = 0;

        int i = length1 - 1, j = length2 - 1;
        while(i >= 0 || j >= 0)
        {
            if(i >= 0 && j >= 0)
            {
                int resultInt = (s1[i] - '0') + (s2[j] - '0') + one;
                result += (resultInt%10) + '0';
                one = (resultInt >= 10)? 1:0;
                j--;
                i--;
            }
            else if(i >= 0)
            {
                int resultInt = (s1[i] - '0') + one;
                result += (resultInt%10) + '0';
                one = (resultInt >= 10)? 1:0;
                i--;
            }
            else if(j >= 0)
            {
                int resultInt = (s2[j] - '0') + one;
                result += (resultInt%10) + '0';
                one = (resultInt >= 10)? 1:0;
                j--;
            }
        }
        if(one != 0) result += '1';
        return reverse(result);
    }

    void addZeros(string& result, int k)
    {
        for(int i = 0; i < k; i++)
        result += '0';
    }

    string multiplyStringByChars(string s1, char ch, int k)
    {
        string result;
        addZeros(result, k);
        int one = 0;
        int length = s1.size();

        for(int i = length - 1; i >= 0; i--)
        {
            int resultInt = (s1[i] - '0') * (ch - '0') + one;
            result += (resultInt % 10) + '0';
            one = resultInt/10;
        }

        if(one != 0) result += one + '0';
        return reverse(result);
    }

    string multiply(string num1, string num2) {

        if(num1 == "0" || num2 == "0") return "0";
        int length2 = num2.size();
        string result = multiplyStringByChars(num1, num2[length2 - 1], 0);
        for(int i = length2 - 2; i >= 0; i--)
        {      
            string currResult = multiplyStringByChars(num1, num2[i], length2 - i - 1);
            result = sumStrings(result, currResult);
        }

        return result;
    }
};
21639