<p>Convert a non-negative integer <code>num</code> to its English words representation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = 123
<strong>Output:</strong> &quot;One Hundred Twenty Three&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = 12345
<strong>Output:</strong> &quot;Twelve Thousand Three Hundred Forty Five&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = 1234567
<strong>Output:</strong> &quot;One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {

private:
    unordered_map<int, string> integer_to_word_map;
    string getWordsForSegment(string input) {
        if (input.length() == 1) {
            int value = input[0] - '0';
            return integer_to_word_map[value];
        } else if (input.length() == 2) {
            int second_digit = input[1] - '0';
            int first_digit = input[0] - '0';
            if (first_digit == 0 and second_digit == 0) {
                return "";
            }
            int first_digit_search = first_digit * 10;
            int total = first_digit_search + second_digit;
            if (total > 20 and total != 30 and total != 40 and total != 50 and
                total != 60 and total != 70 and total != 80 and total != 90) {
                return integer_to_word_map[first_digit_search] + " " +
                       integer_to_word_map[second_digit];
            } else {
                return integer_to_word_map[total];
            }

        } else {
            if (input == "000") {
                return "";
            }
            string first = input.substr(0, 1);
            string second = input.substr(1, 2);

            if (first == "0") {
                return getWordsForSegment(second);
            } else if (first != "0" and second != "00") {
                return getWordsForSegment(first) + " Hundred " +
                       getWordsForSegment(second);
            } else {
                return getWordsForSegment(first) + " Hundred";
            }
        }
        return "";
    }

    string getMultiplier(int segMentNo) {
        if (segMentNo == 1) {
            return "Hundread";
        } else if (segMentNo == 2) {
            return "Thousand";
        } else if (segMentNo == 3) {
            return "Million";
        } else if (segMentNo == 4) {
            return "Billion";
        }
        return "";
    }

public:
    Solution() {
        integer_to_word_map[0] = "Zero";
        integer_to_word_map[1] = "One";
        integer_to_word_map[2] = "Two";
        integer_to_word_map[3] = "Three";
        integer_to_word_map[4] = "Four";
        integer_to_word_map[5] = "Five";
        integer_to_word_map[6] = "Six";
        integer_to_word_map[7] = "Seven";
        integer_to_word_map[8] = "Eight";
        integer_to_word_map[9] = "Nine";
        integer_to_word_map[10] = "Ten";
        integer_to_word_map[11] = "Eleven";
        integer_to_word_map[12] = "Twelve";
        integer_to_word_map[13] = "Thirteen";
        integer_to_word_map[14] = "Fourteen";
        integer_to_word_map[15] = "Fifteen";
        integer_to_word_map[16] = "Sixteen";
        integer_to_word_map[17] = "Seventeen";
        integer_to_word_map[18] = "Eighteen";
        integer_to_word_map[19] = "Nineteen";
        integer_to_word_map[20] = "Twenty";
        integer_to_word_map[30] = "Thirty";
        integer_to_word_map[40] = "Forty";
        integer_to_word_map[50] = "Fifty";
        integer_to_word_map[60] = "Sixty";
        integer_to_word_map[70] = "Seventy";
        integer_to_word_map[80] = "Eighty";
        integer_to_word_map[90] = "Ninety";
    }

    string numberToWords(int num) {
        string output = "";
        string input_str = to_string(num);

        int multiplier = 0;
        int counter = 0;
        string segment = "";
        for (int i = input_str.length() - 1; i >= 0; --i) {
            segment = input_str[i] + segment;
            counter++;
            if (counter == 3) {
                multiplier++;
                // cout << segment << endl;
                string word = getWordsForSegment(segment);

                //  cout << output << endl;
                if (multiplier > 1 and word.length() > 0) {
                    string multiplier_str = getMultiplier(multiplier);
                    word = word + " " + multiplier_str;
                }
                if (word.length() > 0) {
                    output = (output.length() > 0) ? word + " " + output : word;
                }
                segment = "";
                counter = 0;
            }
        }
        if (counter > 0) {
            multiplier++;
            string word = getWordsForSegment(segment);
            if (multiplier > 1 and word.length() > 0) {
                string multiplier_str = getMultiplier(multiplier);
                word = word + " " + multiplier_str;
            }
            if (word.length() > 0) {
                output = (output.length() > 0) ? word + " " + output : word;
            }
        }

        return output;
    }
};
13800