273. Integer to English Words

Problem Statement

link: LeetCode.cn LeetCode Convert a non-negative integer num to its English words representation.

Example:

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

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

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

Constraints: 0 <= num <= 2^31 - 1

Solution Approach

The solution recursively breaks down the number into manageable parts, converts each part to its English words representation, and assembles these parts with appropriate place values to form the final result.

Algorithm

1. Recursive Breakdown: The solution uses a recursive approach to convert numbers less than 1000 into English words, handling units, teens, and tens separately.
2. Handling Large Numbers: It processes the number in chunks of thousands (thousand, million, billion) by iterating through each segment and converting it into words, then appending the appropriate place value.
3. Edge Case Handling: The solution includes special handling for zero, ensuring that it returns “Zero” when the input is 0, and uses string manipulation to manage spaces and formatting in the final output.

   Complexity

   time complexity: O(1) space complexity: O(1)

Implement

    singles = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["", "Thousand", "Million", "Billion"]
class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"

        def recursion(num: int) -> str:
            s = ""
            if num == 0:
                return s
            elif num < 10:
                s += singles[num] + " "
            elif num < 20:
                s += teens[num - 10] + " "
            elif num < 100:
                s += tens[num // 10] + " " + recursion(num % 10)
            else:
                s += singles[num // 100] + " Hundred " + recursion(num % 100)
            return s

        s = ""
        unit = int(1e9)
        for i in range(3, -1, -1):
            curNum = num // unit
            if curNum:
                num -= curNum * unit
                s += recursion(curNum) + thousands[i] + " "
            unit //= 1000
        return s.strip()

    
    

Twitter  facebook  Email