<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:
    # Python3: Dictionaries are ordered by insertion
    wordMap = {
        1000000000: "Billion", 1000000: "Million", 1000: "Thousand",
        100: "Hundred", 90: "Ninety", 80: "Eighty", 70: "Seventy",
        60: "Sixty", 50: "Fifty", 40: "Forty", 30: "Thirty",
        20: "Twenty", 19: "Nineteen", 18: "Eighteen", 17: "Seventeen",
        16: "Sixteen", 15: "Fifteen", 14: "Fourteen", 13: "Thirteen",
        12: "Twelve", 11: "Eleven", 10: "Ten", 9: "Nine", 8: "Eight",
        7: "Seven", 6: "Six", 5: "Five", 4: "Four", 3: "Three",
        2: "Two", 1: "One"
    }

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"

        for denomination in self.wordMap.keys():
            if num >= denomination:
                # Get prefix
                prefix = ""
                if num >= 100:
                    prefix = self.numberToWords(num // denomination) + " "

                # Get current unit
                unit = self.wordMap[denomination]

                # Get suffix, aka from the remainder
                suffix = ""
                if num % denomination > 0:
                    suffix = " " + self.numberToWords(num % denomination)

                return prefix + unit + suffix

        return ""

        # lessThan20Map = { 0: "", 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"}
        # tensMap = { 0: "", 1: "Ten", 2: "Twenty", 3: "Thirty", 4: "Forty", 5: "Fifty",
        #             6: "Sixty", 7: "Seventy", 8: "Eighty", 9: "Ninety"}
        # thousandsMap = { 0: "", 1: "Thousand", 2: "Million", 3: "Billion" }

        # def getWords(n):
        #     if n == 0:
        #         return ""
        #     elif n < 20:
        #         return [lessThan20Map[n]]
        #     elif n < 100:
        #         return [tensMap[n // 10]] + getWords(n % 10)
        #     else:
        #         return [lessThan20Map[n // 100], "Hundred"] + getWords(n % 100)

        # i = 0
        # res = []
        # while num > 0:
        #     if num % 1000 != 0:
        #         res = getWords(num % 1000) + [thousandsMap[i]] + res
        #         num = num // 1000
        #         i += 1

        # return " ".join(res).strip()
16500