<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:
    string trim(const string& str) {
    string result = str;

    result.erase(result.begin(), find_if(result.begin(), result.end(), [](unsigned char ch) {
        return !isspace(ch);
    }));

    result.erase(find_if(result.rbegin(), result.rend(), [](unsigned char ch) {
        return !isspace(ch);
    }).base(), result.end());

    return result;
}
    string numberToWords(int num) {
        if(num==0)  return "Zero";
        unordered_map<int,string> d = {
            {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"},
            {100, "Hundred"},
            {1000, "Thousand"},
            {1000000, "Million"},
            {1000000000, "Billion"}
        };
        // group three chars
        string number = to_string(num);
        int n = number.size();
        int k = 0;
        string ans ="";
        vector<string> place = {"","Thousand", "Million", "Billion"};
        for(int i = n-1;i>=0;i--){
            //ans = place[k++] + ans;
            //ans= " "+ans;
            int j = 0;
            string temp ="";
            while(i>=0 && j<2){
                temp = number[i]+temp;
                i--;
                j++;
            }
            //cout<<temp;
            int two_dig = stoi(temp);
            if(two_dig|| (number[i]-'0'>0))  {
                ans = place[k] + ans;
                ans = " "+ans;
            }
            k++;
            if(d[two_dig]!=""){
                ans = d[two_dig] + ans;
                ans = " "+ans;
            }
            else if(two_dig!=0){
                ans = d[temp[1]-'0']+ ans;
                ans = " "+ans;
                ans =d[(temp[0]-'0')*10]+ ans;
                ans= " "+ans;
            }
            //cout<<ans<<endl;
            if(i<0) break;
            if((number[i]-'0')!=0){
                ans = "Hundred" + ans;
                ans = " "+ans;
            }
            if(d[number[i]-'0']!=""){
                ans = d[number[i]-'0'] + ans;
                ans = " "+ans;
            }
            //cout<<d[number[i]-'0'];
        }
        ans = trim(ans);
        return ans;
    }
};
13400