Skip to main content
Talentd

Vowel Spellchecker - Solution & Explanation

MediumArrayHash TableString19 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

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"
  • 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)

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 <= 5000
  • 1 <= wordlist[i].length, queries[i].length <= 7
  • wordlist[i] and queries[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.

Approach 1: Hash Maps for Different Match Types

This approach uses three types of hash maps:

  • Exact Match: This stores the words in their original form for exact matching.
  • Case-Insensitive Map: This converts all words to lowercase for handling capitalization errors and maps them to their original form for case restoration.
  • Vowel-Insensitive Map: This converts all vowels in words to a placeholder (e.g., '*'), enabling matching words that differ only by vowel substitutions.
For each query, the spellchecker checks in the order of exact matches, case-insensitive matches, and vowel-insensitive matches and returns the first match found.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Trie with Search Functions for Different Match Types

This approach utilizes a trie data structure to accommodate the various search conditions:

  • Exact Match: Regular trie for exact word representation.
  • Case-Insensitive Match: Insert both the lowercase and original version in the trie and search in case-insensitive fashion.
  • Vowel-Insensitive Match: Insert words into the trie after transforming their vowels to a common character, like '*'.
For each query, iterate through trie searches, trying to find matches in the priority of exact matches, case-insensitive matches, and vowel-insensitive matches.

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(N), to store the dictionaries for the wordlist.

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.
Space Complexity: O(N), for storing each transformed mapping in the maps used.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Maps for Different Match TypesO(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 SearchO(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.

Video Solution

Vowel Spellchecker | Simple Approach | Leetcode 966 | codestorywithMIK • codestorywithMIK • 10,082 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Vowel Spellchecker easy or hard?
Vowel Spellchecker is rated Medium difficulty. The challenge comes from implementing three different matching rules while preserving dictionary order and ensuring efficient lookups. Understanding hash-based normalization makes the solution straightforward.
Vowel Spellchecker Python/Java solution
Python and Java implementations typically follow the hash map strategy. Convert words to lowercase, create a devoweled pattern by replacing vowels with '*', and store the first occurrence in maps. Each query is normalized and checked against these structures to determine the correct output.
How to solve Vowel Spellchecker in O(n)?
Strict O(n) is not possible because each string must be processed character by character. The closest optimal approach is O(n + q·L). Preprocess the dictionary by storing exact words, lowercase mappings, and devoweled versions where vowels are replaced with '*'. Each query then performs constant-time hash lookups after normalization.
What is the best approach for Vowel Spellchecker?
The hash map approach with three lookup structures is the most efficient and commonly expected solution. Use a set for exact matches, a lowercase map for case-insensitive matches, and a vowel-normalized map where vowels are replaced with a placeholder like '*'. Each query checks these in order, producing an overall time complexity of O(n + q·L).
Is Vowel Spellchecker asked at Google/Amazon/Meta?
Vowel Spellchecker is a medium-level string and hash table problem similar to questions asked in Google, Amazon, and Meta interviews. It tests normalization techniques, dictionary lookups, and handling multiple matching rules efficiently.
What data structure is used in Vowel Spellchecker?
The primary data structure is a hash table. Multiple hash maps store different normalized versions of each word: exact strings, lowercase versions, and vowel-masked patterns. Some alternative solutions also use a Trie to organize dictionary words for structured search.
What is the time complexity of Vowel Spellchecker?
The optimal hash map solution runs in O(n + q·L) time where n is the number of dictionary words, q is the number of queries, and L is the average word length. Preprocessing the wordlist takes O(n·L), and each query requires O(L) normalization plus constant-time hash lookups.

Ready to solve this problem?

Practice Vowel Spellchecker with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays