LeetCode 题解工作台
元音拼写检查器
在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。 对于给定的查询单词 query ，拼写检查器将会处理两类拼写错误： 大小写：如果查询匹配单词列表中的某个单词（ 不区分大小写 ），则返回的正确单词与单词列表中的大小写相同。 例如： wordlist…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们遍历 ，将单词按照大小写不敏感、元音不敏感的规则分别存入哈希表 和 中，其中 的键为单词的小写形式， 的键为将单词的元音字母替换为 `*` 后的字符串，值为单词本身。用哈希表 存储 中的单词。 遍历 ，对于每个单词 ，如果 在 中，说明 在 中，直接将 加入答案数组 中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。
对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：
- 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
- 例如：
wordlist = ["yellow"],query = "YellOw":correct = "yellow" - 例如：
wordlist = ["Yellow"],query = "yellow":correct = "Yellow" - 例如：
wordlist = ["yellow"],query = "yellow":correct = "yellow"
- 例如：
- 元音错误：如果在将查询单词中的元音
('a', 'e', 'i', 'o', 'u')分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。- 例如：
wordlist = ["YellOw"],query = "yollow":correct = "YellOw" - 例如：
wordlist = ["YellOw"],query = "yeellow":correct = ""（无匹配项） - 例如：
wordlist = ["YellOw"],query = "yllw":correct = ""（无匹配项）
- 例如：
此外，拼写检查器还按照以下优先级规则操作：
- 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
- 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 如果该查询在单词列表中没有匹配项，则应返回空字符串。
给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。
示例 1：
输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] 输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
示例 2:
输入：wordlist = ["yellow"], queries = ["YellOw"] 输出：["yellow"]
提示：
1 <= wordlist.length, queries.length <= 50001 <= wordlist[i].length, queries[i].length <= 7wordlist[i]和queries[i]只包含英文字母
解题思路
方法一：哈希表
我们遍历 ，将单词按照大小写不敏感、元音不敏感的规则分别存入哈希表 和 中，其中 的键为单词的小写形式， 的键为将单词的元音字母替换为 * 后的字符串，值为单词本身。用哈希表 存储 中的单词。
遍历 ，对于每个单词 ，如果 在 中，说明 在 中，直接将 加入答案数组 中。
否则，如果 的小写形式在 中，说明 在 中，且大小写不敏感，将 加入答案数组 中。
否则，如果将 的元音字母替换为 * 后的字符串在 中，说明 在 中，且元音不敏感，将 加入答案数组 中。
否则，说明 在 中，且大小写和元音都不敏感，将空字符串加入答案数组 中。
最后返回答案数组 即可。
时间复杂度 ，空间复杂度 。其中 和 分别为 和 的长度。
class Solution:
def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
def f(w):
t = []
for c in w:
t.append("*" if c in "aeiou" else c)
return "".join(t)
s = set(wordlist)
low, pat = {}, {}
for w in wordlist:
t = w.lower()
low.setdefault(t, w)
pat.setdefault(f(t), w)
ans = []
for q in queries:
if q in s:
ans.append(q)
continue
q = q.lower()
if q in low:
ans.append(low[q])
continue
q = f(q)
if q in pat:
ans.append(pat[q])
continue
ans.append("")
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(C) where C is the combined length of all words and queries since each word is processed into multiple hash maps. Space complexity is O(C) for storing sets and maps for exact, case-insensitive, and vowel-error lookups. |
| 空间 | O(\mathcal{C}) |
面试官常问的追问
外企场景- question_mark
Ask how to efficiently handle multiple spelling error types in a single pass.
- question_mark
Probe whether candidate normalization or direct hash lookup is used for vowel-insensitive matches.
- question_mark
Check understanding of precedence rules between exact, case-insensitive, and vowel-error matches.
常见陷阱
外企场景- error
Forgetting to respect the precedence order, returning a vowel-error match before an exact match.
- error
Overwriting earlier wordlist entries when building maps, causing incorrect first-match results.
- error
Incorrectly normalizing vowels, leading to missed matches in the vowel-error step.
进阶变体
外企场景- arrow_right_alt
Allow queries to include punctuation and handle normalization beyond vowels.
- arrow_right_alt
Handle very large wordlists with streaming or disk-based lookup instead of full hash maps.
- arrow_right_alt
Extend vowel-error matching to include consonant errors or phonetic similarity scoring.