LeetCode 966: Vowel Spellchecker

Problem Restatement

We are given:

wordlist
queries

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

1. If the query exactly matches a word in wordlist, return the query itself.
2. Otherwise, if the query matches a word ignoring capitalization, return the first such word from wordlist.
3. Otherwise, if the query matches a word after treating all vowels as interchangeable, return the first such word from wordlist.
4. 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

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:

1. exact match
2. lowercase match
3. 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:

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:

1. Convert to lowercase.
2. 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:

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

case_map[lower] = word

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

vowel_map[pattern] = word

Then answer each query:

1. If query is in exact, return query.
2. Else if lowercase query is in case_map, return case_map[lower].
3. Else if vowel pattern is in vowel_map, return vowel_map[pattern].
4. 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

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: