<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 {
    string powers[4] = {"","Thousand","Million", "Billion"}; 
    unordered_map<int,string>conversion_map; //single and two digits
public:
    string get_english(vector<int>& digits, int idx1, int idx2, int idx3)
    {
        string converted = "";
        if(idx1 >=0 && digits[idx1] !=0 )
        {
            converted = converted + conversion_map[digits[idx1]] + " Hundred";
        }
        int num = 0;
        if(idx2>=0)
        num = num*10 + digits[idx2];
        num = num*10 + digits[idx3];

        if(num==0)
        return converted;
        //num is non zero

        if(converted.length() > 0)
        converted = converted + " ";

        if(conversion_map.find(num)!=conversion_map.end())
            converted += conversion_map[num];
        else
        {
            converted = converted + conversion_map[digits[idx2]*10] + " " +conversion_map[digits[idx3]]  ;
        }
        return converted;
        

    }

    string numberToWords(int num) {
        //convert each three digits to english and add their powers at the end
        //convert num to vector first
        if(num==0)
        return "Zero";
        conversion_map = {{1,"One"},{2,"Two"},{3,"Three"},{4,"Four"},{5,"Five"},{6,"Six"}, {7,"Seven"}, {8,"Eight"}, {9,"Nine"}, {10,"Ten"},{11,"Eleven"},{12,"Twelve"},{13,"Thirteen"},{14,"Fourteen"},{15,"Fifteen"},{16,"Sixteen"},{17,"Seventeen"},{18,"Eighteen"},{19,"Nineteen"},{20,"Twenty"},{30,"Thirty"},{40,"Forty"},{50, "Fifty"},{60,"Sixty"},{70, "Seventy"},{80,"Eighty"},{90,"Ninety"}};
        if(conversion_map.find(num)!=conversion_map.end())
        return conversion_map[num];

        vector<int>digits;
        while(num)
        {
            digits.push_back(num % 10);
            num /= 10;
        }
        reverse(digits.begin(),digits.end());
        int order=0;
        
        //start picking 3 at a time from end
        vector<string>ans;
        int i = digits.size()-1;
        while(i >=0 )
        {
            //pick i,i-1,i-2
            
            string cur = get_english(digits, i-2,i-1,i);
            if(order > 0 && cur.length()>0)
            cur  = cur + " " + powers[order];
            ans.push_back(cur);
            i-=3;
            order++;

        }
        string english = "";
        for(int i=ans.size()-1;i>=0;i--)
        {
            english  = english + ans[i];
            if(i>0 && ans[i-1].length()>0)
            english+=" ";
        }
        
        return english;

    }
};
12800