# LeetCode 966: Vowel Spellchecker

## Problem Restatement

We are given:

```python
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:

```python
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:

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

## Examples

Example 1:

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

Output:

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

Explanation:

```python
"kite"
```

is an exact match, so return `"kite"`.

```python
"Kite"
```

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

```python
"keti"
```

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

```python
"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:

```python
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:

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

Example:

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

Another example:

```python
"keto" -> "keto" -> "k*t*"
```

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

But length still matters.

Example:

```python
"keet" -> "k**t"
```

This differs from:

```python
"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:

```python
case_map[lower] = word
```

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

```python
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:

```python
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

```python
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:

```python
vowels = set("aeiou")
```

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

```python
def devowel(word: str) -> str:
```

It lowercases first, then replaces vowels with `*`.

The exact match set is:

```python
exact = set(wordlist)
```

This supports case-sensitive lookup.

The case-insensitive map stores first matches:

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

The vowel-error map also stores first matches:

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

For each query, we check exact first:

```python
if query in exact:
    answer.append(query)
```

Then case-insensitive match:

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

Then vowel-error match:

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

If nothing matches:

```python
answer.append("")
```

## Testing

```python
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 |