Leetcode:273 Integer to English Words

Question:

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"

You may have noticed I have highlighted a few keywords in the examples. Try to look for some sort of pattern before you proceed.

Intuition

I must need some sort of mapping for unique identifiers like :

# All the words that describe numbers less than 20
one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen
# All the words that describe multiples of ten
ten, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety
# All the words that describe powers of 10
hundred, thousand, million, billion

Realization 1 : At a high level we can figure out the scale of number i.e thousand, million and billion easily.

Realization 2 : In the examples, you will notice a repeating pattern. If we have a function that converts numbers upto a 100 to words for us, we can reuse the logic for subsequent combinations.

Solution :

class Solution:
    def construct(self):
        self.under_nineteen = "Zero, One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Eleven,"\
                          "Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen".split(',')
        self.tens = ", Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety".split(",")
        self.thousand = ", Thousand, Million, Billion".split(",")
    
    def helper(self, number):
        if number == 0:
            return ""
        elif number < 20:
            return self.under_nineteen[number].strip() + " "
        elif number < 100:
            return self.tens[number//10].strip()  + " " + self.helper(number%10)
        else:
            return self.under_nineteen[number//100].strip()  + " Hundred " + self.helper(number%100)
def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        ans = ""
        # construct provides us with a list of words
        self.construct()
        # as we continue to loop over a number, we start with the smallest thousands varation 
        # and go all the way till billion 
        for item in range(len(self.thousand)):
            # the modulo by 1000 helps get numbers in the set of 3
            # if number = 1234567890
            # iteration 1 : number%1000 = 890
            # iteration 2 : number%1000 = 567
            if num % 1000 != 0:
                ans = self.helper(num%1000) +               self.thousand[item].strip() + " " + ans 
            num //= 1000
        return ans.strip()

Runtime : 32 ms , Space : 14.2 MB

Time Complexity : O(N)

We use concatenate ‘+’ here which means everytime the entire length of the string is iterated over. We can further optimize this by using “”.join() instead of string concatenation.

Space Complexity : O(1)

Optimized Solution :

class Solution:
    def construct(self):
        self.under_nineteen = "Zero, One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, Eleven,"\
                          "Twelve, Thirteen, Fourteen, Fifteen, Sixteen, Seventeen, Eighteen, Nineteen".split(',')
        self.tens = ", Ten, Twenty, Thirty, Forty, Fifty, Sixty, Seventy, Eighty, Ninety".split(",")
        self.thousand = ", Thousand, Million, Billion".split(",")
    
    def helper(self, number):
        if number == 0:
            return ""
        elif number < 20:
            return "".join([self.under_nineteen[number].strip() + " "])
        elif number < 100:
            return "".join([self.tens[number//10].strip()," ",self.helper(number%10)])
        else:
            return "".join([self.under_nineteen[number//100].strip()," Hundred ",self.helper(number%100)])
def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        ans = ""
        # construct provides us with a list of words
        self.construct()
        # as we continue to loop over a number, we start with the smallest thousands varation 
        # and go all the way till billion 
        for item in range(len(self.thousand)):
            # the modulo by 1000 helps get numbers in the set of 3
            # like if number = 1234567890
            # iteration 1 : number%1000 = 890
            # iteration 2 : number%1000 = 567
            if num % 1000 != 0:
                ans = "".join([self.helper(num%1000),self.thousand[item].strip()," ",ans])
            num //= 1000
        return ans.strip()

Runtime : 24 ms, Space : 14.2 MB