<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 numberToWords(int num) {
        unordered_map<int, string> numToStr {{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"}}; 

        if (num == 0) return "Zero"; 

        int64_t exp = 1; 
        int n = num; 
        string res; 
        string subRes; 
        int subNum, hTh, tTh, oTh; 
        while (n != 0) {
            subNum = n % 1000; 
            subRes = ""; 

            hTh = subNum / 100; 
            if (hTh != 0) {
                subRes += numToStr[hTh] + " " + numToStr[100] + " "; 
                subNum %= 100; 
            }

            if (numToStr.find(subNum) != numToStr.end()) subRes += numToStr[subNum] + " "; 
            else {
                tTh = subNum / 10; 
                if (tTh != 0) subRes += numToStr[tTh * 10] + " "; 
                oTh = subNum % 10;
                if (oTh != 0) subRes += numToStr[oTh] + " "; 
            }

            if (!subRes.empty()) {
                if (exp != 1) subRes += numToStr[exp] + " "; 
                res = subRes + res; 
            }
            exp *= 1000;
            n /= 1000; 
        }

        res.pop_back();
        return res; 
    }
};
12200