LeetCode 题解工作台
从英文中重建数字
给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（ 0-9 ）。按 升序 返回原始的数字。 示例 1： 输入： s = "owoztneoer" 输出： "012" 示例 2： 输入： s = "fviefuro" 输出： "45" 提示： 1 5 s[i] 为 ["e","g"…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
class Solution: def originalDigits(self, s: str) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给你一个字符串 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保证是一个符合题目要求的字符串
解题思路
方法一
class Solution:
def originalDigits(self, s: str) -> str:
counter = Counter(s)
cnt = [0] * 10
cnt[0] = counter['z']
cnt[2] = counter['w']
cnt[4] = counter['u']
cnt[6] = counter['x']
cnt[8] = counter['g']
cnt[3] = counter['h'] - cnt[8]
cnt[5] = counter['f'] - cnt[4]
cnt[7] = counter['s'] - cnt[6]
cnt[1] = counter['o'] - cnt[0] - cnt[2] - cnt[4]
cnt[9] = counter['i'] - cnt[5] - cnt[6] - cnt[8]
return ''.join(cnt[i] * str(i) for i in range(10))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) where n is the length of the input string, dominated by single-pass counting and deductions. Space complexity is O(1) since the hash table size is fixed at 26 letters and digit counts are constant. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if you can optimize letter counting rather than trying all permutations of words.
- question_mark
Wants you to identify unique characters that map directly to digits before resolving overlaps.
- question_mark
Checks if you can handle edge cases where multiple digits share letters, like 'one' and 'nine'.
常见陷阱
外企场景- error
Failing to deduct overlapping letters after counting unique digits leads to incorrect counts.
- error
Sorting the final digits incorrectly or omitting digits present multiple times.
- error
Assuming all letters are unique to one digit without checking overlaps, which causes errors.
进阶变体
外企场景- arrow_right_alt
Input strings with repeated digit words appearing multiple times, testing counting accuracy.
- arrow_right_alt
Strings missing some digits entirely, requiring robust handling of zeros in counts.
- arrow_right_alt
Extended character sets with additional noise letters not part of digit words, testing filtering.