Problem Breakdown
We are given a dictionary (wordlist) and a list of query words. For each query, we need to find the “correct” spelling from wordlist based on three precedence rules:
- Exact Match: If the query matches a word in
wordlistexactly (case-sensitive), return that specific word. - Case-Insensitive Match: If not an exact match, but matches after converting both to lowercase, return the first such word from
wordlist. - Vowel Error Match: If neither of the above, check if replacing vowels in the query (and matching words) with any vowel makes them equal case-insensitively. Return the first such word found in
wordlist.
If no rules match, return an empty string. The constraints are small enough (, length ), but we must ensure lookups for queries to avoid TLE on large inputs if this were scaled up (though here it’s acceptable).
Intuition
A brute-force approach would iterate through the entire wordlist for every query. This results in a time complexity of , where is queries length and is wordlist length. Given constraints (), this might pass but isn’t optimal.
The key insight is that the matching rules define three distinct “keys” for a single logical entry:
- The exact string itself (for Rule 1).
- The lowercase version of the string (for Rule 2).
- A normalized version where vowels are replaced by ‘a’ or similar (for Rule 3).
Since we need to return the first match from wordlist for Rules 2 and 3, we should pre-process the wordlist into hash maps that store only the first occurrence of each key. This allows us to answer queries in time after an initial preprocessing step.
Approach
- Preprocessing: Iterate through
wordlist. For each word:- Add it to a set for exact matches (to handle Rule 1). Note that since we need the specific string, and duplicates of identical strings are indistinguishable in terms of content, checking existence is sufficient. However, strictly speaking, if multiple identical words exist, any one works. We can just use
queryitself as return value if found exactly. - Create a lowercase key (
word.lower()). If this key doesn’t exist in our case-insensitive map yet, store the original word there (Rule 2 priority: first match wins). - Create a vowel-normalized key (lowercase with vowels replaced by ‘a’). Store if not present (Rule 3 priority: first match wins).
- Add it to a set for exact matches (to handle Rule 1). Note that since we need the specific string, and duplicates of identical strings are indistinguishable in terms of content, checking existence is sufficient. However, strictly speaking, if multiple identical words exist, any one works. We can just use
- Query Processing: For each query in
queries:- Check exact set/wordlist membership? Actually, since we need to return the specific word from list for Rule 1, and duplicates of identical strings are functionally equivalent, checking if
queryis present in a Set of words found so far works. But wait, Example 1 output"kite"implies returning the string itself. If exact match exists, simply returnquery. - Check case-insensitive map using
query.lower(). Return value if found. - Check vowel-normalized map using normalized query key. Return value if found.
- Else return "".
- Check exact set/wordlist membership? Actually, since we need to return the specific word from list for Rule 1, and duplicates of identical strings are functionally equivalent, checking if
Complexity Analysis
- Time: , where is wordlist length and is queries length. Preprocessing takes linear time relative to total characters in
wordlist. Query processing takes constant amortized time per query (hashing strings of max length 7). - Space: to store the three maps/sets for unique words encountered.
Solution
class Solution:
def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
# Helper function to normalize vowels for Rule 3 (Vowel Errors)
def is_vowel(char):
return char.lower() in {'a', 'e', 'i', 'o', 'u'}
def get_normalized(word):
lower_word = word.lower()
normalized_chars = []
for c in lower_word:
if is_vowel(c):
normalized_chars.append('a') # Replace all vowels with 'a'
else:
normalized_chars.append(c)
return "".join(normalized_chars)
exact_set = set()
case_insensitive_map = {}
vowel_error_map = {}
for word in wordlist:
lower_word = word.lower()
# Rule 1: Exact Match (Case-sensitive).
# We store the query itself if it exists, but since we return 'query' on match,
# a set is sufficient to check existence. However, duplicates of identical strings don't matter.
exact_set.add(word)
# Rule 2 & 3: Case-insensitive and Vowel-error maps only store the FIRST occurrence
if lower_word not in case_insensitive_map:
case_insensitive_map[lower_word] = word
vowel_key = get_normalized(lower_word)
if vowel_key not in vowel_error_map:
vowel_error_map[vowel_key] = word
answer = []
for query in queries:
# Rule 1: Exact Match (Case-sensitive)
if query in exact_set:
answer.append(query)
continue
# Rule 2: Case-Insensitive Match
lower_query = query.lower()
if lower_query in case_insensitive_map:
answer.append(case_insensitive_map[lower_query])
continue
# Rule 3: Vowel Error Match
vowel_key = get_normalized(lower_query)
if vowel_key in vowel_error_map:
answer.append(vowel_error_map[vowel_key])
return answer
Edge Cases Handled
- Exact Matches: The code checks exact matches first. If
queryis identical to a word in the list, it returns immediately without checking other rules (precedence). - Case Sensitivity: Lowercase maps handle Rule 2 correctly by only storing the first occurrence of a lowercase form encountered during preprocessing, ensuring “return the first such match” requirement.
- Vowel Replacement: The helper function normalizes vowels to ‘a’ consistently for both query and wordlist checks, handling mixed case (e.g.,
query=“yollow”, list=["YellOw"]). - No Match: If none of the conditions are met after checking all three maps/sets, an empty string is appended.