<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 {
private:
    // returns first n chars
    string getFirstN(string s, int n) {
        return s.substr(0, n);
    }

    // returns string excluding first n chars
    string removeFirstN(string s, int n) {
        return s.substr(n, s.length());
    }

    // returns num1 >= num2
    bool greaterEqual(string num1, string num2) {
        // check if one is longer first
        if (num1.length() > num2.length())
            return true;
        if (num2.length() > num1.length())
            return false;
        // check each value
        for (int i = 0; i < num2.length(); i++) {
            if (num1[i] > num2[i])
                return true;
            else if (num1[i] < num2[i])
                return false;
        }
        return true;
    }

    // returns num1 - num2 or num2 - num1
    string subtract(string num1, string num2)
    {
        // ensure num1 >= num2
        if (!greaterEqual(num1, num2)) {
            string tmp = num2;
            num2 = num1;
            num1 = tmp;
        }
        // reverse both values to not have to backtrack with carry
        num1 = string(num1.rbegin(), num1.rend());
        num2 = string(num2.rbegin(), num2.rend());

        int carry = 0;
        string result = "";

        // perform num1 - num2
        for (int i = 0; i < num2.length(); i++) {
            int sum = num1[i] - num2[i] - carry;
            // carry value if not enough here
            carry = 0;
            if (sum < 0) {
                sum += 10;
                carry = 1;
            }
            result += sum + '0';
        }

        // add the rest of num1 to result with carry
        for (int i = num2.length(); i < num1.length(); i++) {
            int sum = num1[i] - carry;
            // carry value if not enough here
            carry = 0;
            if (sum < '0') {
                sum += 10;
                carry = 1;
            }
            result += sum;
        }
        // reverse and return result
        return string(result.rbegin(), result.rend());
    }

    // function to add two strings as numbers
    string add(string num1, string num2) {
        int carry = 0;
        string result = "";

        int length = max(num1.length(), num2.length());

        for (int i = 0; i < length; ++i) {
            int sum = carry;
            if (i < num1.length())
                sum += num1[num1.length() - 1 - i] - '0';
            if (i < num2.length())
                sum += num2[num2.length() - 1 - i] - '0';
            carry = sum / 10;
            result = to_string(sum % 10) + result;
        }
        // add last carry if needed
        if (carry > 0)
            result = to_string(carry) + result;
        return result;
    }

    string addTrailingZeros(string s, int n) {
        return s + string(n, '0');
    }

    string mult(string num1, string num2) {
        // multiplication table 0 - 9 x 0 - 9
        int multable[10][10] = {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
            {0, 2, 4, 6, 8, 10, 12, 14, 16, 18},
            {0, 3, 6, 9, 12, 15, 18, 21, 24, 27},
            {0, 4, 8, 12, 16, 20, 24, 28, 32, 36},
            {0, 5, 10, 15, 20, 25, 30, 35, 40, 45},
            {0, 6, 12, 18, 24, 30, 36, 42, 48, 54},
            {0, 7, 14, 21, 28, 35, 42, 49, 56, 63},
            {0, 8, 16, 24, 32, 40, 48, 56, 64, 72},
            {0, 9, 18, 27, 36, 45, 54, 63, 72, 81}
        };

        // find index representation of nums
        int i1 = num1[0] - '0';
        int i2 = num2[0] - '0';

        // return product from table
        return std::to_string(multable[i1][i2]);
    }

    string pad(string s, int n) {
        return string(n - s.size(), '0') + s;
    }

    string removeLeadingZero(string s) {
        return s.erase(0, s.find_first_not_of('0'));
    }

    string karatsuba(string num1, string num2) {
        int n = max(num1.length(), num2.length());
        // Base case: numbers of length 1
        if (n <= 1)
            return mult(num1, num2);

        // ensure both numbers even length
        if (n % 2 != 0)
            n++;

        // pad to ensure equal lengths
        num1 = pad(num1, n);
        num2 = pad(num2, n);

        int n_2 = n / 2;

        // break down strings
        string a = getFirstN(num1, n_2);
        string b = removeFirstN(num1, n_2);
        string c = getFirstN(num2, n_2);
        string d = removeFirstN(num2, n_2);

        // find ac
        string ac = karatsuba(a, c);

        // find bd
        string bd = karatsuba(b, d);

        // find ad + bc
        //string ad_bc = add(karatsuba(a, d), karatsuba(b, c));
        string ad_bc = karatsuba(add(a, b), add(c, d));
        ad_bc = subtract(subtract(ad_bc, ac), bd);

        // find result
        string result = addTrailingZeros(ac, n_2 * 2);
        result = add(result, addTrailingZeros(ad_bc, n_2));
        result = add(result, bd);
        return removeLeadingZero(result);
    }

public:
    string multiply(string num1, string num2) {
        // ensure lengths are even, if not, pad
        if (num1.length() % 2 != 0)
            num1 = '0' + num1;
        if (num2.length() % 2 != 0)
            num2 = '0' + num2;
        // find result
        string result = karatsuba(num1, num2);
        // remove leading 0's
        int startIndex = 0;
        while (result[startIndex] == '0')
            startIndex++;
        if (startIndex >= result.length())
            return "0";
        return result.substr(startIndex);
    }
};
27505