原文链接: https://leetcode-cn.com/problems/reconstruct-original-digits-from-english
英文原文
Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.
Example 1:
Input: s = "owoztneoer" Output: "012"
Example 2:
Input: s = "fviefuro" Output: "45"
Constraints:
1 <= s.length <= 105s[i]is one of the characters["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].sis guaranteed to be valid.
中文题目
给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
示例 1：
输入：s = "owoztneoer" 输出："012"
示例 2：
输入：s = "fviefuro" 输出："45"
提示：
1 <= s.length <= 105s[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)$
其他「模拟」相关内容
考虑加练如下「模拟」题目 🍭🍭
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 33550 | 54774 | 61.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
