| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
中等 |
|
在给定单词列表 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>元音错误：如果在将查询单词中的元音 <code>('a', 'e', 'i', 'o', 'u')</code> 分别替换为任何元音后，能与单词列表中的单词匹配（<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] 得到的正确单词。
示例 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]只包含英文字母
遍历 wordlist，将单词按照大小写不敏感、元音不敏感的规则分别存入哈希表 low 和 pat 中，其中 low 的键为单词的小写形式，pat 的键为将单词的元音字母替换为 * 后的字符串，值为单词本身。用哈希表 s 存储 wordlist 中的单词。
遍历 queries，对于每个单词 q，如果 q 在 s 中，说明 q 在 wordlist 中，直接将 q 加入答案数组 ans 中；否则，如果 q 的小写形式在 low 中，说明 q 在 wordlist 中，且大小写不敏感，将 low[q.lower()] 加入答案数组 ans 中；否则，如果将 q 的元音字母替换为 * 后的字符串在 pat 中，说明 q 在 wordlist 中，且元音不敏感，将 pat[f(q)] 加入答案数组 ans 中；否则，说明 q 在 wordlist 中，且大小写和元音都不敏感，将空字符串加入答案数组 ans 中。
最后返回答案数组 ans 即可。
时间复杂度 wordlist 和 queries 的长度。
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 ansclass Solution {
public String[] spellchecker(String[] wordlist, String[] queries) {
Set<String> s = new HashSet<>();
Map<String, String> low = new HashMap<>();
Map<String, String> pat = new HashMap<>();
for (String w : wordlist) {
s.add(w);
String t = w.toLowerCase();
low.putIfAbsent(t, w);
pat.putIfAbsent(f(t), w);
}
int m = queries.length;
String[] ans = new String[m];
for (int i = 0; i < m; ++i) {
String q = queries[i];
if (s.contains(q)) {
ans[i] = q;
continue;
}
q = q.toLowerCase();
if (low.containsKey(q)) {
ans[i] = low.get(q);
continue;
}
q = f(q);
if (pat.containsKey(q)) {
ans[i] = pat.get(q);
continue;
}
ans[i] = "";
}
return ans;
}
private String f(String w) {
char[] cs = w.toCharArray();
for (int i = 0; i < cs.length; ++i) {
char c = cs[i];
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
cs[i] = '*';
}
}
return String.valueOf(cs);
}
}class Solution {
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> s(wordlist.begin(), wordlist.end());
unordered_map<string, string> low;
unordered_map<string, string> pat;
auto f = [](string& w) {
string res;
for (char& c : w) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
res += '*';
} else {
res += c;
}
}
return res;
};
for (auto& w : wordlist) {
string t = w;
transform(t.begin(), t.end(), t.begin(), ::tolower);
if (!low.count(t)) {
low[t] = w;
}
t = f(t);
if (!pat.count(t)) {
pat[t] = w;
}
}
vector<string> ans;
for (auto& q : queries) {
if (s.count(q)) {
ans.emplace_back(q);
continue;
}
transform(q.begin(), q.end(), q.begin(), ::tolower);
if (low.count(q)) {
ans.emplace_back(low[q]);
continue;
}
q = f(q);
if (pat.count(q)) {
ans.emplace_back(pat[q]);
continue;
}
ans.emplace_back("");
}
return ans;
}
};func spellchecker(wordlist []string, queries []string) (ans []string) {
s := map[string]bool{}
low := map[string]string{}
pat := map[string]string{}
f := func(w string) string {
res := []byte(w)
for i := range res {
if res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i] == 'u' {
res[i] = '*'
}
}
return string(res)
}
for _, w := range wordlist {
s[w] = true
t := strings.ToLower(w)
if _, ok := low[t]; !ok {
low[t] = w
}
if _, ok := pat[f(t)]; !ok {
pat[f(t)] = w
}
}
for _, q := range queries {
if s[q] {
ans = append(ans, q)
continue
}
q = strings.ToLower(q)
if s, ok := low[q]; ok {
ans = append(ans, s)
continue
}
q = f(q)
if s, ok := pat[q]; ok {
ans = append(ans, s)
continue
}
ans = append(ans, "")
}
return
}