LeetCode Solutions Blog

Integer to English Words

Difficulty: Hard

Problem Description

Convert a non-negative integer num to its English words representation.

Key Insights

The problem requires converting integer values into their corresponding English word representations.
We need to handle different magnitudes (units, thousands, millions, etc.) and the special cases for numbers between 1 and 19, as well as tens.
The solution can be implemented using recursion or iterative methods to break down the number into manageable parts.

Space and Time Complexity

Time Complexity: O(n) where n is the number of digits in the number. Space Complexity: O(1) because we are using a constant amount of space for the output string and variables.

Solution

The solution involves creating mappings for numbers to their corresponding English words, particularly focusing on units (0-19), tens (20, 30, ..., 90), and the larger scales (thousand, million, billion). The algorithm recursively divides the number into segments that correspond to these mappings. By handling each segment separately and combining the results, we can construct the complete English representation.

Code Solutions

def numberToWords(num):
    if num == 0:
        return "Zero"

    def one(num):
        switcher = {
            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"
        }
        return switcher.get(num)

    def two_less_20(num):
        return one(num) if num < 20 else ten(num)

    def ten(num):
        switcher = {
            20: "Twenty", 30: "Thirty", 40: "Forty", 50: "Fifty",
            60: "Sixty", 70: "Seventy", 80: "Eighty", 90: "Ninety"
        }
        ten_str = ""
        if num % 10 != 0:
            ten_str = " " + one(num % 10)
        return switcher.get(num - num % 10) + ten_str

    def three(num):
        hundred = ""
        if num >= 100:
            hundred = one(num // 100) + " Hundred"
        return hundred + (" " + two_less_20(num % 100) if num % 100 != 0 else "")

    billion = num // 1000000000
    million = (num // 1000000) % 1000
    thousand = (num // 1000) % 1000
    remainder = num % 1000

    result = ""
    if billion:
        result += three(billion) + " Billion"
    if million:
        result += (" " if result else "") + three(million) + " Million"
    if thousand:
        result += (" " if result else "") + three(thousand) + " Thousand"
    if remainder:
        result += (" " if result else "") + three(remainder)

    return result.strip()