Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123 Output: "One Hundred Twenty Three"
Example 2:
Input: num = 12345 Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:
Input: num = 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Example 4:
Input: num = 1234567891 Output: "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 00, and the second will be empty because there is also no such thing as "Ten One", "Ten Two", etc.
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 [100, 999] so we will need to add a "Hundred" to the string.
if num < 1000:
quotient, remainder = num // 100, num % 100
return [below_twenty[quotient], "Hundred"] + dfs(remainder)
Otherwise, the number is in the range of [1000, 4294967295] 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.
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))