Description#
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] and queries[i] consist only of only English letters.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| 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
}
|
