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:
wordlist = ["yellow"], query = "YellOw": correct = "yellow"wordlist = ["Yellow"], query = "yellow": correct = "Yellow"wordlist = ["yellow"], query = "yellow": correct = "yellow"('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.
wordlist = ["YellOw"], query = "yollow": correct = "YellOw"wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)wordlist = ["YellOw"], query = "yllw": correct = "" (no match)In addition, the spell checker operates under the following precedence rules:
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.The key idea in #966 Vowel Spellchecker is to simulate the spellchecker rules in priority order: exact match, case-insensitive match, and vowel error match. Efficient lookup is achieved using hash tables.
First, store all words in a set to quickly detect exact matches. Next, create a map from the lowercase version of each word to its first occurrence in the word list. This helps resolve case-insensitive queries. Finally, build another hash map where each word is converted to a vowel-normalized form (for example, replacing vowels with a placeholder like *). This structure allows matching queries that differ only by vowel substitutions.
For each query, check the rules sequentially: exact match, lowercase match, then vowel-normalized match. If none exist, return an empty string. With preprocessing and constant-time lookups using hash maps, the solution efficiently handles all queries.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set + Hash Map with Vowel Normalization | O(W * L + Q * L) | O(W * L) |
Greg Hogg
This approach uses three types of hash maps:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), to store the dictionaries for the wordlist.
1def spellChecker(wordlist, queries):
2 def normalize_word(word):
3 return ''.join(['*' if c in 'aeiouAEIOU' else c for c in word])
4 exact_matches = set(wordlist)
5 case_matches = {w.lower(): w for w in reversed(wordlist)}
6 vowel_matches = {}
7 for w in reversed(wordlist):
8 vw = normalize_word(w.lower())
9 if vw not in vowel_matches:
10 vowel_matches[vw] = w
11 def find_match(query):
12 if query in exact_matches:
13 return query
14 low_query = query.lower()
15 if low_query in case_matches:
16 return case_matches[low_query]
17 vow_query = normalize_word(low_query)
18 if vow_query in vowel_matches:
19 return vowel_matches[vow_query]
20 return ""
21 return [find_match(query) for query in queries]This solution initializes three dictionaries for exact, case-insensitive, and vowel-insensitive matches. The normalize_word function transforms words by replacing all vowels with '*'. For each query, the solution checks the query against these dictionaries and returns results based on the first successful match.
This approach utilizes a trie data structure to accommodate the various search conditions:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), for storing each transformed mapping in the maps used.
1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Spellchecker {
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> exactMatch(wordlist.begin(), wordlist.end());
unordered_map<string, string> caseInsensitiveMap;
unordered_map<string, string> vowelInsensitiveMap;
for (auto it = wordlist.rbegin(); it != wordlist.rend(); ++it) {
string lowerWord = toLower(*it);
caseInsensitiveMap[lowerWord] = *it;
vowelInsensitiveMap[maskVowels(lowerWord)] = *it;
}
vector<string> results;
for (const string& query : queries) {
if (exactMatch.count(query)) {
results.push_back(query);
} else {
string lowerQuery = toLower(query);
string vowelMaskedQuery = maskVowels(lowerQuery);
if (caseInsensitiveMap.count(lowerQuery)) {
results.push_back(caseInsensitiveMap[lowerQuery]);
} else if (vowelInsensitiveMap.count(vowelMaskedQuery)) {
results.push_back(vowelInsensitiveMap[vowelMaskedQuery]);
} else {
results.push_back("");
}
}
}
return results;
}
private:
string toLower(const string& word) {
string res = word;
transform(res.begin(), res.end(), res.begin(), ::tolower);
return res;
}
string maskVowels(string word) {
for (char& c : word) {
if (isVowel(c)) c = '*';
}
return word;
}
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of problem is common in interviews because it tests string manipulation, hashing, and rule-based matching logic. Companies often use similar problems to evaluate practical use of hash maps.
The optimal approach uses hash tables to enforce the matching priority: exact match, case-insensitive match, and vowel-error match. Preprocessing the word list into normalized forms allows fast lookups for each query.
Vowel normalization replaces all vowels (a, e, i, o, u) in a lowercase word with a placeholder like '*'. This allows different vowel variations of a word to map to the same key for quick matching.
Hash-based structures such as sets and hash maps work best. They allow constant-time lookups for exact words, lowercase forms, and vowel-normalized patterns.
This C++ solution builds maps for case-insensitive and vowel-insensitive matches from the wordlist. During querying, each query is transformed and searched against these data structures in the order of priority. It offers a clean way to handle multiple match types while efficiently searching.