LeetCode 966: Vowel Spellchecker

Problem Restatement

We are given:

wordlist
queries

For each query, return the corrected word according to these priority rules:

If the query exactly matches a word in wordlist, return the query itself.
Otherwise, if the query matches a word ignoring capitalization, return the first such word from wordlist.
Otherwise, if the query matches a word after treating all vowels as interchangeable, return the first such word from wordlist.
Otherwise, return an empty string.

The vowels are:

a, e, i, o, u

The official constraints allow up to 5000 words and 5000 queries, with word and query lengths up to 7.

Input and Output

Item	Meaning
Input	`wordlist`, the valid dictionary words
Input	`queries`, the words to check
Output	A list of corrected words
Exact match	Case-sensitive match
Case match	Same letters after lowercasing
Vowel match	Same pattern after lowercasing and replacing vowels

Example function shape:

def spellchecker(wordlist: list[str], queries: list[str]) -> list[str]:
    ...

Examples

Example 1:

wordlist = ["KiTe", "kite", "hare", "Hare"]
queries = ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"]

Output:

["kite", "KiTe", "KiTe", "Hare", "hare", "", "", "KiTe", "", "KiTe"]

Explanation:

"kite"

is an exact match, so return "kite".

"Kite"

has no exact match, but it matches "KiTe" ignoring capitalization. Since "KiTe" appears first in wordlist, return "KiTe".

"keti"

matches "KiTe" by vowel error, because after lowercasing and replacing vowels, both become:

"k*t*"

So return "KiTe".

First Thought: Scan the Wordlist for Every Query

For each query, we could scan every word in wordlist.

For each word, check:

exact match
lowercase match
vowel-pattern match

This works logically, but it repeats too much work.

With up to 5000 words and 5000 queries, scanning the full wordlist for every query gives:

O(len(wordlist) * len(queries) * word_length)

We can preprocess the wordlist instead.

Key Insight

The matching rules have fixed priority.

So we build three lookup structures:

Structure	Key	Value
`exact`	Original word	Original word
`case_map`	Lowercase word	First original word with that lowercase form
`vowel_map`	Lowercase word with vowels replaced	First original word with that vowel pattern

The phrase “first such match” matters. For case_map and vowel_map, we should only store the first word seen for each key.

Vowel Pattern

To handle vowel errors, normalize each word like this:

Convert to lowercase.
Replace every vowel with a marker such as *.

Example:

"KiTe" -> "kite" -> "k*t*"

Another example:

"keto" -> "keto" -> "k*t*"

So "keto" can match "KiTe" by vowel error.

But length still matters.

Example:

"keet" -> "k**t"

This differs from:

"kite" -> "k*t*"

So "keet" does not match "KiTe".

Algorithm

Preprocess wordlist.

For each word:

Add it to exact.
Compute lower = word.lower().
If lower is not in case_map, store:

case_map[lower] = word

Compute the vowel pattern.
If the pattern is not in vowel_map, store:

vowel_map[pattern] = word

Then answer each query:

If query is in exact, return query.
Else if lowercase query is in case_map, return case_map[lower].
Else if vowel pattern is in vowel_map, return vowel_map[pattern].
Else return "".

Correctness

The algorithm checks the same priority order required by the problem.

First, it checks exact matches using the original query string. If this succeeds, returning the query is correct because exact matches have highest priority.

If there is no exact match, it checks the lowercase form. The case_map stores the first word in wordlist for each lowercase spelling. Therefore, if a case-insensitive match exists, the algorithm returns the first such match.

If there is no case-insensitive match, it checks the vowel-normalized form. The vowel_map stores the first word in wordlist for each pattern where lowercase vowels are replaced by the same marker. Two words have the same pattern exactly when they match after treating vowels as interchangeable. Therefore, the algorithm returns the first valid vowel-error match.

If all three checks fail, then no allowed rule can match the query, so returning "" is correct.

Thus, every query is answered according to the required precedence rules.

Complexity

Let:

w = len(wordlist)
q = len(queries)
L = maximum word length

Metric	Value	Why
Time	`O((w + q) * L)`	Each word and query is normalized a constant number of times
Space	`O(w * L)`	The maps store normalized forms of wordlist entries

Implementation

class Solution:
    def spellchecker(
        self,
        wordlist: list[str],
        queries: list[str],
    ) -> list[str]:
        vowels = set("aeiou")

        def devowel(word: str) -> str:
            chars = []

            for char in word.lower():
                if char in vowels:
                    chars.append("*")
                else:
                    chars.append(char)

            return "".join(chars)

        exact = set(wordlist)
        case_map = {}
        vowel_map = {}

        for word in wordlist:
            lower = word.lower()
            pattern = devowel(word)

            if lower not in case_map:
                case_map[lower] = word

            if pattern not in vowel_map:
                vowel_map[pattern] = word

        answer = []

        for query in queries:
            if query in exact:
                answer.append(query)
                continue

            lower = query.lower()

            if lower in case_map:
                answer.append(case_map[lower])
                continue

            pattern = devowel(query)

            if pattern in vowel_map:
                answer.append(vowel_map[pattern])
            else:
                answer.append("")

        return answer

Code Explanation

We define vowels once:

vowels = set("aeiou")

The helper function converts a word into its vowel-insensitive form:

def devowel(word: str) -> str:

It lowercases first, then replaces vowels with *.

The exact match set is:

exact = set(wordlist)

This supports case-sensitive lookup.

The case-insensitive map stores first matches:

if lower not in case_map:
    case_map[lower] = word

The vowel-error map also stores first matches:

if pattern not in vowel_map:
    vowel_map[pattern] = word

For each query, we check exact first:

if query in exact:
    answer.append(query)

Then case-insensitive match:

if lower in case_map:
    answer.append(case_map[lower])

Then vowel-error match:

if pattern in vowel_map:
    answer.append(vowel_map[pattern])

If nothing matches:

answer.append("")

Testing

def run_tests():
    s = Solution()

    assert s.spellchecker(
        ["KiTe", "kite", "hare", "Hare"],
        ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"],
    ) == ["kite", "KiTe", "KiTe", "Hare", "hare", "", "", "KiTe", "", "KiTe"]

    assert s.spellchecker(
        ["yellow"],
        ["YellOw"],
    ) == ["yellow"]

    assert s.spellchecker(
        ["YellOw"],
        ["yollow", "yeellow", "yllw"],
    ) == ["YellOw", "", ""]

    assert s.spellchecker(
        ["Apple", "apple"],
        ["apple", "APPLE", "appli"],
    ) == ["apple", "Apple", "Apple"]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Main example	Checks all priority rules
Case-insensitive match	Returns original wordlist casing
Vowel examples	Checks vowel replacement and length mismatch
Duplicate lowercase forms	Exact match beats case match, first case match is preserved