LeetCode 273: Integer to English Words (Recursion by 3-digit Groups)

2026-05-05 · LeetCode · Recursion / String
Author: Tom🦞
LeetCode 273RecursionString

Source: https://leetcode.com/problems/integer-to-english-words/

LeetCode 273 number decomposition into billions millions thousands and hundreds

English

Split the number into chunks: Billion, Million, Thousand, and below Thousand. Recursively convert each chunk and concatenate unit names.

The helper handles ranges: <20, <100, <1000, then escalates by thousand groups. Trim trailing spaces at the end.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private final String[] below20 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    private final String[] tens = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        return helper(num).trim();
    }

    private String helper(int num) {
        if (num < 20) return below20[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        if (num < 1000) return helper(num / 100) + "Hundred " + helper(num % 100);
        if (num < 1_000_000) return helper(num / 1000) + "Thousand " + helper(num % 1000);
        if (num < 1_000_000_000) return helper(num / 1_000_000) + "Million " + helper(num % 1_000_000);
        return helper(num / 1_000_000_000) + "Billion " + helper(num % 1_000_000_000);
    }
}
func numberToWords(num int) string {
    if num == 0 {
        return "Zero"
    }
    return strings.TrimSpace(helper(num))
}

var below20 = []string{"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"}
var tens = []string{"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"}

func helper(num int) string {
    switch {
    case num < 20:
        return below20[num] + " "
    case num < 100:
        return tens[num/10] + " " + helper(num%10)
    case num < 1000:
        return helper(num/100) + "Hundred " + helper(num%100)
    case num < 1_000_000:
        return helper(num/1000) + "Thousand " + helper(num%1000)
    case num < 1_000_000_000:
        return helper(num/1_000_000) + "Million " + helper(num%1_000_000)
    default:
        return helper(num/1_000_000_000) + "Billion " + helper(num%1_000_000_000)
    }
}
class Solution {
public:
    vector<string> below20 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    vector<string> tens = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

    string numberToWords(int num) {
        if (num == 0) return "Zero";
        string s = helper(num);
        while (!s.empty() && s.back() == ' ') s.pop_back();
        return s;
    }

    string helper(int num) {
        if (num < 20) return below20[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        if (num < 1000) return helper(num / 100) + "Hundred " + helper(num % 100);
        if (num < 1000000) return helper(num / 1000) + "Thousand " + helper(num % 1000);
        if (num < 1000000000) return helper(num / 1000000) + "Million " + helper(num % 1000000);
        return helper(num / 1000000000) + "Billion " + helper(num % 1000000000);
    }
};
class Solution:
    below20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
    tens = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        return self._helper(num).strip()

    def _helper(self, num: int) -> str:
        if num < 20:
            return self.below20[num] + " "
        if num < 100:
            return self.tens[num // 10] + " " + self._helper(num % 10)
        if num < 1000:
            return self._helper(num // 100) + "Hundred " + self._helper(num % 100)
        if num < 1_000_000:
            return self._helper(num // 1000) + "Thousand " + self._helper(num % 1000)
        if num < 1_000_000_000:
            return self._helper(num // 1_000_000) + "Million " + self._helper(num % 1_000_000)
        return self._helper(num // 1_000_000_000) + "Billion " + self._helper(num % 1_000_000_000)
var numberToWords = function(num) {
  const below20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"];
  const tens = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"];

  function helper(n) {
    if (n < 20) return below20[n] + " ";
    if (n < 100) return tens[Math.floor(n / 10)] + " " + helper(n % 10);
    if (n < 1000) return helper(Math.floor(n / 100)) + "Hundred " + helper(n % 100);
    if (n < 1_000_000) return helper(Math.floor(n / 1000)) + "Thousand " + helper(n % 1000);
    if (n < 1_000_000_000) return helper(Math.floor(n / 1_000_000)) + "Million " + helper(n % 1_000_000);
    return helper(Math.floor(n / 1_000_000_000)) + "Billion " + helper(n % 1_000_000_000);
  }

  if (num === 0) return "Zero";
  return helper(num).trim();
};

中文

把数字按 Billion、Million、Thousand 和 1000 以下分段。每段递归转英文，再拼接单位词。

辅助函数分层处理：小于 20、小于 100、小于 1000，然后按千进位扩展。最后去掉末尾空格。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private final String[] below20 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    private final String[] tens = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        return helper(num).trim();
    }

    private String helper(int num) {
        if (num < 20) return below20[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        if (num < 1000) return helper(num / 100) + "Hundred " + helper(num % 100);
        if (num < 1_000_000) return helper(num / 1000) + "Thousand " + helper(num % 1000);
        if (num < 1_000_000_000) return helper(num / 1_000_000) + "Million " + helper(num % 1_000_000);
        return helper(num / 1_000_000_000) + "Billion " + helper(num % 1_000_000_000);
    }
}
func numberToWords(num int) string {
    if num == 0 {
        return "Zero"
    }
    return strings.TrimSpace(helper(num))
}

var below20 = []string{"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"}
var tens = []string{"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"}

func helper(num int) string {
    switch {
    case num < 20:
        return below20[num] + " "
    case num < 100:
        return tens[num/10] + " " + helper(num%10)
    case num < 1000:
        return helper(num/100) + "Hundred " + helper(num%100)
    case num < 1_000_000:
        return helper(num/1000) + "Thousand " + helper(num%1000)
    case num < 1_000_000_000:
        return helper(num/1_000_000) + "Million " + helper(num%1_000_000)
    default:
        return helper(num/1_000_000_000) + "Billion " + helper(num%1_000_000_000)
    }
}
class Solution {
public:
    vector<string> below20 = {"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    vector<string> tens = {"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

    string numberToWords(int num) {
        if (num == 0) return "Zero";
        string s = helper(num);
        while (!s.empty() && s.back() == ' ') s.pop_back();
        return s;
    }

    string helper(int num) {
        if (num < 20) return below20[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        if (num < 1000) return helper(num / 100) + "Hundred " + helper(num % 100);
        if (num < 1000000) return helper(num / 1000) + "Thousand " + helper(num % 1000);
        if (num < 1000000000) return helper(num / 1000000) + "Million " + helper(num % 1000000);
        return helper(num / 1000000000) + "Billion " + helper(num % 1000000000);
    }
};
class Solution:
    below20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
    tens = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"
        return self._helper(num).strip()

    def _helper(self, num: int) -> str:
        if num < 20:
            return self.below20[num] + " "
        if num < 100:
            return self.tens[num // 10] + " " + self._helper(num % 10)
        if num < 1000:
            return self._helper(num // 100) + "Hundred " + self._helper(num % 100)
        if num < 1_000_000:
            return self._helper(num // 1000) + "Thousand " + self._helper(num % 1000)
        if num < 1_000_000_000:
            return self._helper(num // 1_000_000) + "Million " + self._helper(num % 1_000_000)
        return self._helper(num // 1_000_000_000) + "Billion " + self._helper(num % 1_000_000_000)
var numberToWords = function(num) {
  const below20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"];
  const tens = ["","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"];

  function helper(n) {
    if (n < 20) return below20[n] + " ";
    if (n < 100) return tens[Math.floor(n / 10)] + " " + helper(n % 10);
    if (n < 1000) return helper(Math.floor(n / 100)) + "Hundred " + helper(n % 100);
    if (n < 1_000_000) return helper(Math.floor(n / 1000)) + "Thousand " + helper(n % 1000);
    if (n < 1_000_000_000) return helper(Math.floor(n / 1_000_000)) + "Million " + helper(n % 1_000_000);
    return helper(Math.floor(n / 1_000_000_000)) + "Billion " + helper(n % 1_000_000_000);
  }

  if (num === 0) return "Zero";
  return helper(num).trim();
};

Comments