LC 423. 从英文中重建数字

题目描述

这是 LeetCode 上的 423. 从英文中重建数字 ，难度为 中等。

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

示例 1：

输入：s = "owoztneoer"

输出："012"

示例 2：

输入：s = "fviefuro"

输出："45"

提示：

• $1 <= s.length <= 10^5$
• s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
• s 保证是一个符合题目要求的字符串

---

模拟

题目要求我们将打乱的英文单词重建为数字。

我们可以先对 s 进行词频统计，然后根据「英文单词中的字符唯一性」确定构建的顺序，最后再对答案进行排序即可。

具体的，zero 中的 z 在其余所有单词中都没出现过，我们可以先统计 zero 的出现次数，并构建 $0$；然后观察剩余数字，其中 eight 中的 g 具有唯一性，构建 $8$；再发现 six 中的 x 具有唯一性，构建 $6$；发现 three 中的 h 具有唯一性（利用在此之前 eight 已经被删除干净，词频中仅存在 three 对应的 h)，构建 $3$ …

最终可以确定一个可行的构建序列为 0, 8, 6, 3, 2, 7, 5, 9, 4, 1。

代码：

class Solution {
    static String[] ss = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    static int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
    public String originalDigits(String s) {
        int n = s.length();
        int[] cnts = new int[26];
        for (int i = 0; i < n; i++) cnts[s.charAt(i) - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char c : ss[i].toCharArray()) k = Math.min(k, cnts[c - 'a']);
            for (char c : ss[i].toCharArray()) cnts[c - 'a'] -= k;
            while (k-- > 0) sb.append(i);
        }
        char[] cs = sb.toString().toCharArray();
        Arrays.sort(cs);
        return String.valueOf(cs);
    }
}

• 时间复杂度：令 $m$ 为最终答案的长度，$L$ 为所有英文单词的字符总长度。构建答案的复杂度为 $O(L + m)$；对构建答案进行排序复杂度为 $O(m\log{m})$。整体复杂度为 $O(m\log{m})$
• 空间复杂度：$O(L + m)$

---

最后

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

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

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

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