Convert a non-negative integer `num`

to its English words representation.

**Example 1:**

Input:num = 123Output:"One Hundred Twenty Three"

**Example 2:**

Input:num = 12345Output:"Twelve Thousand Three Hundred Forty Five"

**Example 3:**

Input:num = 1234567Output:"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

**Example 4:**

Input:num = 1234567891Output:"One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

**Constraints:**

`0 <= num <= 2^31 - 1`

The description was taken from https://leetcode.com/problems/integer-to-english-words/.

`#O(N) Time, O(N) Space Where N is Number of Digits`

**class** **Solution**:

**def** **numberToWords**(self, num: int) -> str:

suffixes = [

"Thousand", "Million", "Billion"]

` tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy",`

"Eighty", "Ninety"]

` below_twenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven",`

"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",

"Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen",

"Nineteen" ]

**def** **dfs**(num:int) -> List[str]:

**if** num == **0**:

**return** []

**if** num < **20**:

**return** [below_twenty[num]]

**if** num < **100**:

quotient, remainder = num // **10**, num % **10**

**return** [tens[quotient]] + dfs(remainder)

**if** num < **1000**:

quotient, remainder = num // **100**, num % **100**

**return** [below_twenty[quotient], "Hundred"] + dfs(remainder)

**for** power, suffix **in** enumerate(suffixes, **1**):

**if** num < **1000 **** (power + **1**):

place = **1000 **** power

quotient, remainder = num // place, num % place

**return** dfs(quotient) + [suffix] + dfs(remainder)

**if** **not** num:

**return** "Zero"

**return** " ".join(dfs(num))

We can solve this by partitioning the numbers through recursion within a Depth-First Search manner.

We will section output words into three separate arrays, then use those for converting the greatest portion of the number and passing off any remainders to lower function calls within the recursive tree.

Let's start by building our suffixes list for the bigger values, our tens list, and the remaining values between one and nineteen.

Having arrays instead of HashMaps will allow us to use each index as the lookup value, but one thing to note here is that the first two elements in the tens list will be empty and the first element in the below twenty list will be empty as well.

The first element in the tens list will be empty because there

, and the second will be empty because there is also no such thing as "Ten One", "Ten Two", etc.**00**

` suffixes = [`

"Thousand", "Million", "Billion"]

` tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy",`

"Eighty", "Ninety"]

` below_twenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven",`

"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",

"Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen",

"Nineteen" ]

Next, we will make our recursive, DFS function that will take a given number input and return the number converted to a list of strings.

` `

**def** **dfs**(num:int) -> List[str]:

If the number input is zero, then we will return an empty list.

` `

**if** num == **0**:

**return** []

If the number is less than twenty, then we will return the corresponding index in the below twenty conversion array.

` `

**if** num < **20**:

**return** [below_twenty[num]]

If the number is less than one hundred, we will take what we can divide evenly, get the corresponding index from the tens conversion array and perform a DFS on the remainder.

` `

**if** num < **100**:

quotient, remainder = num // **10**, num % **10**

**return** [tens[quotient]] + dfs(remainder)

We will do the same thing for a number under one thousand, but if it got to this conditional statement it means that the current number is in the range of

so we will need to add a "Hundred" to the string.**[100, 999]**

` `

**if** num < **1000**:

quotient, remainder = num // **100**, num % **100**

**return** [below_twenty[quotient], "Hundred"] + dfs(remainder)

Otherwise, the number is in the range of

so we will step through the remaining suffix array and utilize their indices as the power to multiply one thousand with and get the corresponding index.**[1000, 4294967295]**

Once we find the first number that is less than the current range, like we were doing in the conditional statements, we will divide what we can evenly, get the prefix by performing a DFS, add the suffix from the iteration, and perform a DFS on the remainder.

This number will be very big so aren't going to be able to just plug it into a conversion array to get the corresponding index, this will likely need to be done several times.

` `

**for** power, suffix **in** enumerate(suffixes, **1**):

**if** num < **1000 **** (power + **1**):

place = **1000 **** power

quotient, remainder = num // place, num % place

**return** dfs(quotient) + [suffix] + dfs(remainder)

If the input number was zero, we will just convert it to a string directly.

` `

**if** **not** num:

**return** "Zero"

Otherwise, we will run a DFS on the input number, join all of the arrays together to form a string, and return that string.

` `

**return** " ".join(dfs(num))