Domain 2MediumMEDIUM

Vowel Spellchecker

LeetCode problem 966: Vowel Spellchecker (medium).

Domain: medium•Updated: 2026-09-05
#Hash Table#String

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:

  1. Exact Match: If the query matches a word in wordlist exactly (case-sensitive), return that specific word.
  2. Case-Insensitive Match: If not an exact match, but matches after converting both to lowercase, return the first such word from wordlist.
  3. 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 (N≤5000N \le 5000, length ≤7\le 7), but we must ensure O(1)O(1) 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 O(Q×N×L)O(Q \times N \times L), where QQ is queries length and NN is wordlist length. Given constraints (50002=25M5000^2 = 25M), this might pass but isn’t optimal.

The key insight is that the matching rules define three distinct “keys” for a single logical entry:

  1. The exact string itself (for Rule 1).
  2. The lowercase version of the string (for Rule 2).
  3. 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 O(1)O(1) time after an initial preprocessing step.

Approach

  1. 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 query itself 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).
  2. 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 query is 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 return query.
    • 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 "".

Complexity Analysis

  • Time: O(N⋅L+Q⋅L)O(N \cdot L + Q \cdot L), where NN is wordlist length and QQ 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: O(N⋅L)O(N \cdot L) 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 query is 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.