Algorithm
Problem Name: 966. Vowel Spellchecker
Problem Link: https://leetcode.com/problems/vowel-spellchecker/
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.
- Example:
wordlist = ["yellow"],query = "YellOw":correct = "yellow" - Example:
wordlist = ["Yellow"],query = "yellow":correct = "Yellow" - Example:
wordlist = ["yellow"],query = "yellow":correct = "yellow"
- Example:
- Vowel Errors: If after replacing the vowels
('a', 'e', 'i', 'o', 'u')of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.- Example:
wordlist = ["YellOw"],query = "yollow":correct = "YellOw" - Example:
wordlist = ["YellOw"],query = "yeellow":correct = ""(no match) - Example:
wordlist = ["YellOw"],query = "yllw":correct = ""(no match)
- Example:
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.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String[] spellchecker(String[] wordlist, String[] queries) {
Map capsMap = new HashMap<>();
Map < String, String> vowMap = new HashMap<>();
Set perfect = new HashSet<>();
for (String word : wordlist) {
perfect.add(word);
capsMap.putIfAbsent(word.toLowerCase(), word);
vowMap.putIfAbsent(getVowelKey(word.toLowerCase()), word);
}
String[] ans = new String[queries.length];
for (int i = 0; i < queries.length; i++) {
if (perfect.contains(queries[i])) {
ans[i] = queries[i];
}
else if (capsMap.containsKey(queries[i].toLowerCase())) {
ans[i] = capsMap.get(queries[i].toLowerCase());
}
else {
ans[i] = vowMap.getOrDefault(getVowelKey(queries[i].toLowerCase()), "");
}
}
return ans;
}
private String getVowelKey(String word) {
StringBuilder sb = new StringBuilder();
for (char c : word.toCharArray()) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
sb.append('*');
}
else {
sb.append(c);
}
}
return sb.toString();
}
}
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"]
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def spellchecker(self, wordlist, queries):
"""
:type wordlist: List[str]
:type queries: List[str]
:rtype: List[str]
"""
st, cap, vow = set(wordlist), {}, {}
for w in wordlist:
newC = w.lower()
newW = "".join(c if c not in "aeiou" else "*" for c in newC)
if newC not in cap:
cap[newC] = w
if newW not in vow:
vow[newW] = w
for i, w in enumerate(queries):
if w in st:
pass
elif w.lower() in cap:
queries[i] = cap[w.lower()]
else:
new = "".join(c if c not in "aeiou" else "*" for c in w.lower())
if new in vow:
queries[i] = vow[new]
else:
queries[i] = ""
return queries
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"]