<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 {
public:
    vector<string> ones = {"One ","Two ","Three ","Four ","Five ","Six ","Seven ","Eight ","Nine "};
    vector<string> teens = {"Ten ","Eleven ","Twelve ","Thirteen ","Fourteen ","Fifteen ","Sixteen ","Seventeen ","Eighteen ","Nineteen "};
    vector<string> tens = {"Twenty ","Thirty ","Forty ","Fifty ","Sixty ","Seventy ","Eighty ","Ninety "};
    string hundred = "Hundred ";
    string thousand = "Thousand ";
    string million = "Million ";
    string billion = "Billion ";
    string zero = "Zero";
    unordered_map<int, string> 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 "}};
    
    string word(int num)
    {
        string result;
       // cout<<"n:"<<num<<" ";
        if(num/100 !=0)
        {
            result += map[num/100];
            result += hundred;
        }
        num = num %100;
        if(num>19)
        {
            int o = num%10;
            num = num -o;
            result += map[num];
            result += map[o];
        }
        else
        {
            result += map[num];
        }
        //cout<<result<<endl;
        return result;
       
    }
    string digitword(vector<int> digits)
    {
        string result;
        int len = digits.size();
        if(len ==3)
        {
            if(digits.back() != 0)
            {
                result += ones[digits.back()-1];
                result += hundred;
            }
            digits.pop_back();
            len--;
        }
        if(len ==2)
        {
            int tdigit = digits.back();
            digits.pop_back();
            
            if(tdigit ==1)
            {
                result += teens[digits.back()];
                digits.pop_back();
                len --;
            }
            if(tdigit>1)
            {
                result += tens[tdigit-2];
            }
            len--;
        }
        if(len ==1)
        {
            if(digits.back() !=0)
            result += ones[digits.back()-1];
            digits.pop_back();
            len--;
        }
        
        return result;
    }

    string numberToWords(int num) {
        string result;
        vector<int> digits;
        if(num==0) return zero;

        if(num/1000000000)
        {
            result += word(num/1000000000);
            result += billion;
            num = num % 1000000000;
        }
        
        if(num/1000000)
        {
            result += word(num/1000000);
            result += million;
            num = num % 1000000;
        }
        
        if(num/1000)
        {
            result += word(num/1000);
            result += thousand;
            num = num % 1000;
        }
        
        if(num)
        {
            result+= word(num);
        }
        result.pop_back();
        return result;
        while(num>0)
        {
            int m = num %1000;
            int n = m%100;
            
        }
        while(num>0)
        {
            digits.push_back(num%10);
            num = num/10;
        }

        int len = digits.size();
        

        if(len>9)
        {
            int bdigits = len-9;
            vector<int> d(digits.end()-bdigits,digits.end());
            result += digitword(d);
            result += billion;
            while(bdigits>0)
            {
                digits.pop_back();
                bdigits--;
            }
            len=9;
        }
        if(len>6)
        {
            int bdigits = len-6;
            vector<int> d(digits.end()-bdigits,digits.end());
            string s = digitword(d);
            if(s!="")
            {
                result += s;
                result += million;
            }
            
            while(bdigits>0)
            {
                digits.pop_back();
                bdigits--;
            }
            len=6;
        }
        if(len>3)
        {
            int bdigits = len-3;
            vector<int> d(digits.end()-bdigits,digits.end());
            string s = digitword(d);
            if(s!="")
            {
                result += s;
                result += thousand;
            }
            
            while(bdigits>0)
            {
                digits.pop_back();
                bdigits--;
            }
            len=3;
        }
        if(len<=3)
        {
            result += digitword(digits);
        }
        result.pop_back();
        return result;
    }
};
13100