Vowel Spellchecker - Video Solutions

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.