英文原文
Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.
For a given query word, the spell checker handles two categories of spelling mistakes:
- Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
<ul> <li>Example: <code>wordlist = ["yellow"]</code>, <code>query = "YellOw"</code>: <code>correct = "yellow"</code></li> <li>Example: <code>wordlist = ["Yellow"]</code>, <code>query = "yellow"</code>: <code>correct = "Yellow"</code></li> <li>Example: <code>wordlist = ["yellow"]</code>, <code>query = "yellow"</code>: <code>correct = "yellow"</code></li> </ul> </li> <li>Vowel Errors: If after replacing the vowels <code>('a', 'e', 'i', 'o', 'u')</code> of the query word with any vowel individually, it matches a word in the wordlist (<strong>case-insensitive</strong>), then the query word is returned with the same case as the match in the wordlist. <ul> <li>Example: <code>wordlist = ["YellOw"]</code>, <code>query = "yollow"</code>: <code>correct = "YellOw"</code></li> <li>Example: <code>wordlist = ["YellOw"]</code>, <code>query = "yeellow"</code>: <code>correct = ""</code> (no match)</li> <li>Example: <code>wordlist = ["YellOw"]</code>, <code>query = "yllw"</code>: <code>correct = ""</code> (no match)</li> </ul> </li>
In addition, the spell checker operates under the following precedence rules:
- When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
- When the query matches a word up to capitlization, you should return the first such match in the wordlist.
- When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
- If the query has no matches in the wordlist, you should return the empty string.
Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].
Example 1:
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
Example 2:
Input: wordlist = ["yellow"], queries = ["YellOw"] Output: ["yellow"]
Constraints:
1 <= wordlist.length, queries.length <= 50001 <= wordlist[i].length, queries[i].length <= 7wordlist[i]andqueries[i]consist only of only English letters.
中文题目
在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。
对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：
- 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
<ul> <li>例如：<code>wordlist = ["yellow"]</code>, <code>query = "YellOw"</code>: <code>correct = "yellow"</code></li> <li>例如：<code>wordlist = ["Yellow"]</code>, <code>query = "yellow"</code>: <code>correct = "Yellow"</code></li> <li>例如：<code>wordlist = ["yellow"]</code>, <code>query = "yellow"</code>: <code>correct = "yellow"</code></li> </ul> </li> <li>元音错误：如果在将查询单词中的元音（‘a’、‘e’、‘i’、‘o’、‘u’）分别替换为任何元音后，能与单词列表中的单词匹配（<strong>不区分大小写</strong>），则返回的正确单词与单词列表中的匹配项大小写相同。 <ul> <li>例如：<code>wordlist = ["YellOw"]</code>, <code>query = "yollow"</code>: <code>correct = "YellOw"</code></li> <li>例如：<code>wordlist = ["YellOw"]</code>, <code>query = "yeellow"</code>: <code>correct = ""</code> （无匹配项）</li> <li>例如：<code>wordlist = ["YellOw"]</code>, <code>query = "yllw"</code>: <code>correct = ""</code> （无匹配项）</li> </ul> </li>
此外，拼写检查器还按照以下优先级规则操作：
- 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
- 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 如果该查询在单词列表中没有匹配项，则应返回空字符串。
给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。
示例：
输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] 输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
提示：
1 <= wordlist.length <= 50001 <= queries.length <= 50001 <= wordlist[i].length <= 71 <= queries[i].length <= 7wordlist和queries中的所有字符串仅由英文字母组成。
通过代码
官方题解
方法：哈希映射（HashMap）
思路与算法
我们分析了算法需要考虑的 3 种情况: 当查询完全匹配时，当查询存在大小写不同的单词匹配时，当查询与出现元音错误的单词匹配时。
在所有 3 种情况下，我们都可以使用哈希表来查询答案。
- 对于第一种情况（完全匹配），我们使用集合存放单词以有效地测试查询单词是否在该组中。
- 对于第二种情况（大小写不同），我们使用一个哈希表，该哈希表将单词从其小写形式转换为原始单词（大小写正确的形式）。
- 对于第三种情况（元音错误），我们使用一个哈希表，将单词从其小写形式（忽略元音的情况下）转换为原始单词。
该算法仅剩的要求是认真规划和仔细阅读问题。
[MUcCoDbr-Java]class Solution { Set<String> words_perfect; Map<String, String> words_cap; Map<String, String> words_vow; public String[] spellchecker(String[] wordlist, String[] queries) { words_perfect = new HashSet(); words_cap = new HashMap(); words_vow = new HashMap(); for (String word: wordlist) { words_perfect.add(word); String wordlow = word.toLowerCase(); words_cap.putIfAbsent(wordlow, word); String wordlowDV = devowel(wordlow); words_vow.putIfAbsent(wordlowDV, word); } String[] ans = new String[queries.length]; int t = 0; for (String query: queries) ans[t++] = solve(query); return ans; } public String solve(String query) { if (words_perfect.contains(query)) return query; String queryL = query.toLowerCase(); if (words_cap.containsKey(queryL)) return words_cap.get(queryL); String queryLV = devowel(queryL); if (words_vow.containsKey(queryLV)) return words_vow.get(queryLV); return ""; } public String devowel(String word) { StringBuilder ans = new StringBuilder(); for (char c: word.toCharArray()) ans.append(isVowel(c) ? '*' : c); return ans.toString(); } public boolean isVowel(char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); } }
[MUcCoDbr-Python]class Solution(object): def spellchecker(self, wordlist, queries): def devowel(word): return "".join('*' if c in 'aeiou' else c for c in word) words_perfect = set(wordlist) words_cap = {} words_vow = {} for word in wordlist: wordlow = word.lower() words_cap.setdefault(wordlow, word) words_vow.setdefault(devowel(wordlow), word) def solve(query): if query in words_perfect: return query queryL = query.lower() if queryL in words_cap: return words_cap[queryL] queryLV = devowel(queryL) if queryLV in words_vow: return words_vow[queryLV] return "" return map(solve, queries)
复杂度分析
时间复杂度：$O(\mathcal{C})$，其中 $\mathcal{C}$ 是
wordlist和queries中内容的总数。空间复杂度：$O(\mathcal{C})$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 3205 | 7886 | 40.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
