Vowel Spellchecker | Simple Approach | Leetcode 966 | codestorywithMIK
Vowel Spellchecker - Video Solution
Watch 10 video solutions for Vowel Spellchecker, a medium level problem involving Array, Hash Table, String. This walkthrough by codestorywithMIK has 10,082 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Approach Overview
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.
Complexity Analysis
| 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. |