<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 num2word(int num) {
        string ans;
        if (num >= 100) {
            ans.append(digit1[num / 100]);
            ans.append("Hundred ");
            num %= 100;
        }
        if (num >= 10) {
            if (num >= 11 && num <= 19) {
                ans.append(teens[num - 11]); return ans;
            }
            ans.append(digit2[num / 10 - 1]);
            num %= 10;
        }
        if (num > 0) 
            ans.append(digit1[num]);
        return ans;
    }

    string numberToWords(int num) {
        if (num == 0) return "Zero";
        string ans;
        int u = 0;
        while (num) {
            string res = num2word(num % 1000);
            if (u > 0 && res.size() > 0) {
                ans = res + units[u-1] + ans;
            } else ans = res + ans;
            u++;
            num /= 1000;
        }
        if (ans.back() == ' ') ans.pop_back();
        return ans;
    }

private:
    vector<string> digit1 = {"Zero", "One ", "Two ", "Three ", "Four ", "Five ", "Six ", "Seven ", "Eight ", "Nine "};
    vector<string> digit2 = {"Ten ", "Twenty ", "Thirty ", "Forty ", "Fifty ", "Sixty ", "Seventy ", "Eighty ", "Ninety "};
    vector<string> teens = {"Eleven ", "Twelve ", "Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ", "Eighteen ", "Nineteen "};
    vector<string> units = {"Thousand ", "Million ", "Billion "};
};
11600