題目描述

將非負整數（< 2³¹）轉為英文單詞表示。例如：

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

遞歸分治策略

按千位分組（Billion, Million, Thousand, Hundred），遞歸處理每組：

• ≤19：直接查表
• 20~99：十位查表 + 遞歸個位
• 100~999：百位遞歸 + "Hundred" + 遞歸餘數
• ≥1000：對應單位遞歸 + 單位詞 + 遞歸餘數

完整代碼

class Solution {
public:
    string numberToWords(int num) {
        return num2str(num);
    }
private:
    string num2str(int num) {
        if (num == 0) return "Zero"; // 特殊情況
        string res;
        if (num <= 19) {
            res += nums[num];
        } else if (num <= 99) {
            res += tens[num / 10];
            if (num % 10 != 0) res += " " + num2str(num % 10);
        } else if (num <= 999) {
            res += num2str(num / 100) + " Hundred";
            if (num % 100 != 0) res += " " + num2str(num % 100);
        } else if (num <= 999999) {
            res += num2str(num / 1000) + " Thousand";
            if (num % 1000 != 0) res += " " + num2str(num % 1000);
        } else if (num <= 999999999) {
            res += num2str(num / 1000000) + " Million";
            if (num % 1000000 != 0) res += " " + num2str(num % 1000000);
        } else { // ≤ 2,147,483,647
            res += num2str(num / 1000000000) + " Billion";
            if (num % 1000000000 != 0) res += " " + num2str(num % 1000000000);
        }
        return res;
    }

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

關鍵細節

• num == 0 直接返回 "Zero"（遞歸基例）
• 空格處理：只在有餘數時添加空格 + 遞歸結果
• 表驅動：tens 索引 2~9 對應二十~九十，nums 0~19 直接映射
• 遞歸深度 ≤ 4（Billion, Million, Thousand, Hundred），棧安全

複雜度

• 時間：O(log n) 位數遞歸
• 空間：O(log n) 遞歸棧 + 輸出字符串