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.Problem Overview: You receive a wordlist and a list of queries. For each query, return the first word from the dictionary that matches under three rules: exact match, case-insensitive match, or vowel-error match where vowels (a, e, i, o, u) can substitute for each other. If none match, return an empty string.
Approach 1: Hash Maps for Different Match Types (O(n + q·L) time, O(n·L) space)
This approach preprocesses the dictionary using multiple hash-based structures. First, store every word in a set for constant-time exact matching. Then build a map from the lowercase version of each word to the first occurrence in the dictionary to handle case-insensitive matches. Finally, normalize each word by replacing every vowel with a placeholder such as * and store that mapping as well. When processing a query, check the structures in order: exact match, lowercase match, then vowel-normalized match. Each lookup is O(L) for string processing plus O(1) hash lookup, giving total complexity O(n + q·L). This approach relies heavily on hash table lookups and efficient string normalization.
Approach 2: Trie with Search Functions for Different Match Types (O(n·L + q·26^v) time, O(n·L) space)
A Trie stores the dictionary character by character. Each node represents a prefix and keeps track of the earliest word inserted for that path. Exact matches follow the standard Trie traversal. For case-insensitive matching, convert the query to lowercase before traversal. The vowel-error rule requires branching whenever a vowel appears: instead of following a single edge, the search tries all vowel possibilities. While the Trie organizes words efficiently by prefix, vowel substitution can cause multiple branches during search. In the worst case this increases the search space, but typical inputs remain manageable. The structure works well when you want prefix-based organization or when dictionary size is large and reused across many queries. This technique demonstrates how Tries extend common array and string problems into structured search problems.
Recommended for interviews: The hash map approach is the expected solution. It directly models the three matching rules with constant-time lookups and simple preprocessing. Building separate mappings for exact, lowercase, and devoweled forms keeps the logic clean and efficient. The Trie approach is more complex and rarely required in interviews, but it shows deeper understanding of structured search and dictionary matching.
This approach uses three types of hash maps:
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.
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.
This approach utilizes a trie data structure to accommodate the various search conditions:
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.
C++
JavaScript
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.
We traverse the wordlist and store the words in hash tables low and pat according to case-insensitive and vowel-insensitive rules, respectively. The key of low is the lowercase form of the word, and the key of pat is the string obtained by replacing the vowels of the word with *, with the value being the word itself. We use the hash table s to store the words in wordlist.
We traverse queries, for each word q, if q is in s, it means q is in wordlist, and we directly add q to the answer array ans; otherwise, if the lowercase form of q is in low, it means q is in wordlist and is case-insensitive, and we add low[q.lower()] to the answer array ans; otherwise, if the string obtained by replacing the vowels of q with * is in pat, it means q is in wordlist and is vowel-insensitive, and we add pat[f(q)] to the answer array ans; otherwise, it means q is not in wordlist, and we add an empty string to the answer array ans.
Finally, we return the answer array ans.
The time complexity is O(n + m), and the space complexity is O(n), where n and m are the lengths of wordlist and queries, respectively.
| Approach | Complexity |
|---|---|
| Hash Maps for Different Match Types | Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query. |
| Trie with Search Functions for Different Match Types | Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Maps for Different Match Types | O(n + q·L) | O(n·L) | Best general solution. Simple logic and constant-time lookups for exact, case-insensitive, and vowel-normalized matches. |
| Trie with Specialized Search | O(n·L + q·26^v) | O(n·L) | Useful when the dictionary is reused across many searches or when prefix-based matching structures are preferred. |
Vowel Spellchecker | Simple Approach | Leetcode 966 | codestorywithMIK • codestorywithMIK • 9,848 views views
Watch 9 more video solutions →Practice Vowel Spellchecker with our built-in code editor and test cases.
Practice on FleetCode