#966

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Vowel Spellchecker

Implement a spellchecker that matches queries to a wordlist using exact, case-insensitive, and vowel-error rules efficiently.

array hash table string

Problem Statement

You are given a wordlist and a list of query words. Your task is to implement a spellchecker that returns the correct word for each query based on a set of spelling rules. The spellchecker must first attempt exact matches, then case-insensitive matches, and finally matches ignoring vowels. If no match exists, return an empty string.

The spellchecker must prioritize matches in this order: exact match, case-insensitive match, vowel-error match. Vowel errors treat the vowels 'a', 'e', 'i', 'o', 'u' interchangeably. Queries and wordlist entries consist of only English letters, and outputs must respect the earliest match in wordlist when multiple candidates exist.

Examples

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 details omitted.

Example 2

Input: wordlist = ["yellow"], queries = ["YellOw"]

Output: ["yellow"]

Example details omitted.

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.

Solution Approach

Build Exact Match Set

Create a set containing all words in the wordlist to quickly identify queries that exactly match a word. This handles the simplest and highest-priority case efficiently in O(1) per query.

Build Case-Insensitive Map

Map lowercase versions of each word to the first occurrence in the wordlist. When a query fails an exact match, convert it to lowercase and look up this map to handle case-insensitive matches while preserving the earliest appearance.

Build Vowel-Error Normalization Map

Normalize words by replacing all vowels with a placeholder and map each normalized key to its first word occurrence. Queries failing exact and case-insensitive matches are normalized the same way, enabling efficient vowel-error detection while maintaining the proper precedence order.

Complexity Analysis

Metric	Value
Time	O(\mathcal{C})
Space	O(\mathcal{C})

Time complexity is O(C) where C is the combined length of all words and queries since each word is processed into multiple hash maps. Space complexity is O(C) for storing sets and maps for exact, case-insensitive, and vowel-error lookups.

What Interviewers Usually Probe

Ask how to efficiently handle multiple spelling error types in a single pass.
Probe whether candidate normalization or direct hash lookup is used for vowel-insensitive matches.
Check understanding of precedence rules between exact, case-insensitive, and vowel-error matches.

Common Pitfalls or Variants

Common pitfalls

Forgetting to respect the precedence order, returning a vowel-error match before an exact match.
Overwriting earlier wordlist entries when building maps, causing incorrect first-match results.
Incorrectly normalizing vowels, leading to missed matches in the vowel-error step.

Follow-up variants

Allow queries to include punctuation and handle normalization beyond vowels.
Handle very large wordlists with streaming or disk-based lookup instead of full hash maps.
Extend vowel-error matching to include consonant errors or phonetic similarity scoring.

FAQ

What is the best approach for LeetCode 966 Vowel Spellchecker?

Use hash maps for exact matches, lowercase matches, and vowel-error normalization to efficiently resolve queries while respecting precedence.

How do I handle vowels in Vowel Spellchecker without missing matches?

Replace all vowels in both wordlist and query with a placeholder character before lookup to detect vowel-error matches consistently.

Why does order of wordlist matter in this spellchecker?

The first occurrence in wordlist must be returned for matches, so maps must preserve the earliest index when multiple words map to the same key.

What is the time complexity of this approach?

Time complexity is O(C) for building hash maps and scanning all queries, where C is the total length of all words and queries combined.

Can this method handle large query arrays efficiently?

Yes, using hash lookups for each level of matching ensures each query resolves in near O(1) time per lookup.

terminal

Solution

Solution 1: Hash Table

We traverse the $\textit{wordlist}$ and store the words in hash tables $\textit{low}$ and $\textit{pat}$ according to case-insensitive and vowel-insensitive rules, respectively. The key of $\textit{low}$ is the lowercase form of the word, and the key of $\textit{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 $\textit{s}$ to store the words in $\textit{wordlist}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def f(w):
            t = []
            for c in w:
                t.append("*" if c in "aeiou" else c)
            return "".join(t)

        s = set(wordlist)
        low, pat = {}, {}
        for w in wordlist:
            t = w.lower()
            low.setdefault(t, w)
            pat.setdefault(f(t), w)

        ans = []
        for q in queries:
            if q in s:
                ans.append(q)
                continue
            q = q.lower()
            if q in low:
                ans.append(low[q])
                continue
            q = f(q)
            if q in pat:
                ans.append(pat[q])
                continue
            ans.append("")
        return ans

Continue Practicing

#953 verifying an alien dictionary #1002 find common characters #929 unique email addresses