273.Integer to English Words

Tags: [implementation], [pattern]

Com: {fb}

Link: https://leetcode.com/problems/integer-to-english-words/#/description

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231- 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

More clean solution:

class Solution(object):
    def __init__(self):
        # we want 'One' at index 1.
        self.belowTen = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']

        # 10 - 10 = 0, 11 - 10 = 1, 12 - 10 = 2, ...
        # so, we want 'Ten' at index 0, 'Eleven' at index 1, 'Twelve' at index 2, ...
        self.belowTwenty = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen',
                            'Nineteen']

        # 10 / 10 = 1, 20 / 10 = 2, 30 / 10 = 3, ...
        # so, we want 'Ten' at index 1, 'Twenty' at index 2, 'Thirty' at index 3, ...
        self.belowHundred = ['', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']

    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        if not num:
            return 'Zero'

        return self.helper(num)

    def helper(self, num):
        result = ''
        if num < 10:
            result = self.belowTen[num]
        elif num < 20:
            result = self.belowTwenty[num - 10]
        elif num < 100:
            result = self.belowHundred[num / 10] + ' ' + self.helper(num % 10)
        elif num < 1000:
            # how many hundreds
            result = self.helper(num / 100) + ' Hundred ' + self.helper(num % 100)
        elif num < 1000000:
            # how many thousands
            result = self.helper(num / 1000) + ' Thousand ' + self.helper(num % 1000)
        elif num < 1000000000:
            # how many millions
            result = self.helper(num / 1000000) + ' Million ' + self.helper(num % 1000000)
        else:
            # how many billions
            result = self.helper(num / 1000000000) + ' Billion ' + self.helper(num % 1000000000)

        return result.strip()

Note:

• Time complexity = O(n), n is the length of the given num.

Solution: Break to 3 digits chunk

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        if not num:
            return 'Zero'

        units = {
            1: 'One',
            2: 'Two',
            3: 'Three',
            4: 'Four',
            5: 'Five',
            6: 'Six',
            7: 'Seven',
            8: 'Eight',
            9: 'Nine',
            11: 'Eleven',
            12: 'Twelve',
            13: 'Thirteen',
            14: 'Fourteen',
            15: 'Fifteen',
            16: 'Sixteen',
            17: 'Seventeen',
            18: 'Eighteen',
            19: 'Nineteen'
        }

        tens = {
            1: 'Ten',
            2: 'Twenty',
            3: 'Thirty',
            4: 'Forty',
            5: 'Fifty',
            6: 'Sixty',
            7: 'Seventy',
            8: 'Eighty',
            9: 'Ninety'
        }

        section_keywords = ['', 'Thousand', 'Million', 'Billion']

        s = str(num)
        result = []

        section_index = 0
        while len(s) >= 3:
            sub_result = self.helper(int(s[-3:]), units, tens)
            sub_result.reverse()
            if sub_result and section_keywords[section_index]:
                result.append(section_keywords[section_index])
            result += sub_result

            s = s[:-3]
            section_index += 1

        if s:
            sub_result = self.helper(int(s), units, tens)
            sub_result.reverse()
            if sub_result and section_keywords[section_index]:
                result.append(section_keywords[section_index])
            result += sub_result

        result.reverse()
        return ' '.join(result)

    def helper(self, n, units, tens):
        result = []
        if n >= 100:
            result.append(units[n / 100])
            result.append('Hundred')
            n %= 100

        if n in units:
            result.append(units[n])
        else:
            if n / 10 in tens:
                result.append(tens[n / 10])
            if n % 10 in units:
                result.append(units[n % 10])

        return result

Revelation:

• Be careful the case: input = 1000000, the result should be "One Million", which is the reason why each time we need check the following:

if sub_result and section_keywords[section_index]:
    result.append(section_keywords[section_index])

• When the sub_result is empty, we don't need to add section keyword.
• We didn't add the 0=>'Zero' to the units map, which make dealing with some corner case more clean, like the following:

else:
    if n / 10 in tens:
        result.append(tens[n / 10])
    if n % 10 in units:
        result.append(units[n % 10])

• If n is 10, it will only go into the "if n / 10" in tens branch, and append 'Ten' into the result, will not go to "if n % 10 in units" branch.

Note:

• Time complexity = O(n), n is the length of the given num.