<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:
    unordered_map<int, string> belowTen = {{0, ""}, {1, "One "}, {2, "Two "}, {3, "Three "}, {4, "Four "}, {5, "Five "}, {6, "Six "}, {7, "Seven "}, {8, "Eight "}, {9, "Nine "}};
    unordered_map<int, string> belowTwenty = {{11, "Eleven "}, {12, "Twelve "}, {13, "Thirteen "}, {14, "Fourteen "}, {15, "Fifteen "}, {16, "Sixteen "}, {17, "Seventeen "}, {18, "Eighteen "}, {19, "Nineteen "}};
    unordered_map<int, string> belowHun = {{10, "Ten "}, {20, "Twenty "}, {30, "Thirty "}, {40, "Forty "}, {50, "Fifty "}, {60, "Sixty "}, {70, "Seventy "}, {80, "Eighty "}, {90, "Ninety "}};

    string solve(int n) {
        if (n < 10) {
            return belowTen[n];
        }
        if (n < 20 && n > 10) {
            return belowTwenty[n];
        }
        if (n < 100) {
            return belowHun[n / 10 * 10] + belowTen[n % 10];
        }
        if (n < 1000) {// 900
            return belowTen[n / 100] + "Hundred " + ((n % 100 != 0) ? solve(n % 100) : "");
        }
        if (n < 1000000) {
            return solve(n / 1000) + "Thousand " + ((n % 1000 != 0) ? solve(n % 1000) : "");
        }
        if (n < 1000000000) {
            return solve(n / 1000000) + "Million " + ((n % 1000000 != 0) ? solve(n % 1000000) : "");
        }
        return solve(n / 1000000000) + "Billion " + ((n % 1000000000 != 0) ? solve(n % 1000000000) : "");
    }

    string numberToWords(int num) {
        if (num == 0) return "Zero";
        string result = solve(num);
        if (!result.empty() && result.back() == ' ') {
            result.pop_back();
        }
        return result;
    }
};

12900