LC 273. 整数转换英文表示

题目描述

这是 LeetCode 上的 273. 整数转换英文表示 ，难度为 困难。

将非负整数 num 转换为其对应的英文表示。

示例 1：

输入：num = 123

输出："One Hundred Twenty Three"

示例 2：

输入：num = 12345

输出："Twelve Thousand Three Hundred Forty Five"

示例 3：

输入：num = 1234567

输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4：

输入：num = 1234567891

输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

提示：

• $0 <= num <= 2^{31} - 1$

---

模拟

字符串大模拟，重点之一是考察大家对数字英文单词的熟练程度。🤣

首先，英文好的同学自然知道数字表示是每三位一组进行的，英文不好的可能需要通过样例来找找规律。

由于是每三位一组进行表示，首要考虑实现一个 num2Str 函数，将十进制长度小于等于 $3$ 位的数字表示出来，然后在后面配合 Billion、Million 和 Thousand 即可表示出范围不超过 $2^{32}-1$ 的任意数字。

从定义出发 num2Str 需要解决 $[0, 999]$ 范围内的所有整数，但由于该函数需要复用到更大的位数来配合 Billion、Million 和 Thousand，而 Zero Billion 并不是一个合法的描述，因此我们需要将 $0$ 抠出来特判，让 num2Str 对范围在 $[1, 999]$ 的数值进行转换。

考虑如何实现 num2Str，假设当前需要转换的数字为 $x$，我们可以对 $x$ 的大小进行分情况讨论：

1. $x >= 100$：此时首先需要表示成 ??? hundred，表示完后考虑更小的位数；
2. $x >= 20$：此时需要表示成 ??? XXX-ty 的形式，表示完后考虑更小的位数；
3. $x < 20$：直接描述成具体的单词。

实现完 num2Str 后，剩下的只需要考虑如何将入参 $num$ 拆分成每三位一组处理即可。

代码：

class Solution {
    static String[] num2str_small = {
        "Zero", 
        "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
        "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
    };
    static String[] num2str_medium = {
        "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
    };
    static String[] num2str_large = {
        "Billion", "Million", "Thousand", "",
    };
    String num2Str(int x) {
        String ans = "";
        if (x >= 100) {
            ans += num2str_small[x / 100] + " Hundred ";
            x %= 100;
        }
        if (x >= 20) {
            ans += num2str_medium[x / 10] + " ";
            x %= 10;
        }
        if (x != 0) ans += num2str_small[x] + " ";
        return ans;
    }
    public String numberToWords(int num) {
        if (num == 0) return num2str_small[0];
        StringBuilder sb = new StringBuilder();
        for (int i = (int)1e9, j = 0; i >= 1; i /= 1000, j++) {
            if (num < i) continue;
            sb.append(num2Str(num / i) + num2str_large[j] + " ");
            num %= i;
        }
        while (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}

• 时间复杂度：令 $n$ 为 $num$ 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 $num$ 的十进制长度成线性关系，再根据 $num$ 的长度与 $num$ 数值的关系，可得最终复杂度为 $O(\log{n})$
• 空间复杂度：令 $n$ 为 $num$ 数值大小，复杂度取决于最终构建的答案的长度，由于是每三位一组进行处理，同时每三位一组所转换的英文描述有明确的长度上界，因此最终答案长度与 $num$ 的十进制长度成线性关系，再根据 $num$ 的长度与 $num$ 数值的关系，可得最终复杂度为 $O(\log{n})$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.273 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。