<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 
{

    map<int, string> number {{1, "One"}, {2, "Two"}, {3, "Three"}, {4, "Four"}, {5, "Five"}, {6, "Six"}, {7, "Seven"}, {8, "Eight"}, {9, "Nine"}};
    map<int, string> teens {{1, "Eleven"}, {2, "Twelve"}, {3, "Thirteen"}, {4, "Fourteen"}, {5, "Fifteen"}, {6, "Sixteen"}, {7, "Seventeen"}, {8, "Eighteen"}, {9, "Nineteen"}};

    map<int, string> tens {{1, "Ten"}, {2, "Twenty"}, {3, "Thirty"}, {4, "Forty"}, {5, "Fifty"}, {6, "Sixty"}, {7, "Seventy"}, {8, "Eighty"}, {9, "Ninety"}};

    map<int, string> inBetween {{0, ""}, {1, "Thousand"}, {2, "Million"}, {3, "Billion"}};


public:
    string numberToWords(int num) 
    {
        if(num == 0)
        {
            return "Zero";
        }

        string resultString;
        int inbetweenMapIndex = 0;
        //vector<string> finalStringVector;
        while(num)
        {
            int last3num = num % 1000;
            num /= 1000;

            //printf("last3num: %d --  inbetweenMapIndex: %d\n", last3num, inbetweenMapIndex);

            int digit1 = last3num % 10;
            last3num /= 10;

            int digit2 = last3num % 10;
            last3num /= 10;

            int digit3 = last3num % 10;
            last3num /= 10;

            string intermidiateStr = get3PartString(digit3, digit2, digit1);
            //printf("intermidiateStr:  %s \n", intermidiateStr.c_str());
            if(intermidiateStr.size() > 0)
            {
                if(resultString.size() > 0)
                    resultString = intermidiateStr + " " + inBetween[inbetweenMapIndex] + " " + resultString;
                else
                {
                    resultString = intermidiateStr;
                    if(inbetweenMapIndex > 0)
                    {
                        resultString += " " + inBetween[inbetweenMapIndex];
                    }
                }
            }
            inbetweenMapIndex++;
        }

    /*
        printf("finalStringVector size: %d \n", finalStringVector.size());

        int i = finalStringVector.size()-1;
        string resultString = finalStringVector[i];
        i--;
        for(; i >= 0; i--)
        {
            printf("1: %s \n", resultString.c_str());
            resultString += " ";
            resultString += finalStringVector[i]; //str / *+ " "* /;
            printf("2: %s \n", resultString.c_str());
        }
    */
        return resultString;
    }

    string get3PartString(int digit3, int digit2, int digit1)
    {
        //printf("%d %d %d \n", digit3,  digit2,  digit1);
        string numberString;

        if(digit3 != 0)
        {
            numberString = number[digit3];
            numberString += " Hundred";
        }

        if(digit2 == 1 && digit1 != 0)
        {
            if(numberString.size() > 0) numberString += " ";
            numberString += teens[digit1];
        }
        else
        {
            if(digit2 != 0)
            {
                if(numberString.size() > 0) numberString += " ";
                numberString += tens[digit2];
            }

            if(digit1 != 0)
            {
                if(numberString.size() > 0) numberString += " ";
                numberString += number[digit1];
            }
        }

        return numberString;
    }

};

13200