# LeetCode 676: Implement Magic Dictionary

## Problem Restatement

We need to design a data structure called `MagicDictionary`.

It supports two operations:

| Operation | Meaning |
|---|---|
| `buildDict(dictionary)` | Store a list of distinct words |
| `search(searchWord)` | Return whether `searchWord` can become a dictionary word by changing exactly one character |

The important rule is exactly one character must be changed. Zero changes do not count. Two or more changes do not count. The modified word must exist in the dictionary.

For example, if the dictionary contains:

```python
["hello", "leetcode"]
```

Then:

```python
search("hello")    # false
search("hhllo")    # true
search("hell")     # false
search("leetcoded") # false
```

`"hello"` returns `false` because it matches a dictionary word with zero changes.

`"hhllo"` returns `true` because changing the second character from `'h'` to `'e'` gives `"hello"`.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `MagicDictionary()` | None | Creates an empty object |
| `buildDict(dictionary)` | `List[str]` | `None` |
| `search(searchWord)` | `str` | `bool` |

The dictionary words are distinct.

The search operation only allows character replacement. It cannot insert or delete characters. Therefore, only words with the same length as `searchWord` can match.

## Examples

Example:

```python
magicDictionary = MagicDictionary()
magicDictionary.buildDict(["hello", "leetcode"])

magicDictionary.search("hello")      # false
magicDictionary.search("hhllo")      # true
magicDictionary.search("hell")       # false
magicDictionary.search("leetcoded")  # false
```

Explanation:

| Search word | Result | Reason |
|---|---:|---|
| `"hello"` | `false` | Needs zero changes, but exactly one change is required |
| `"hhllo"` | `true` | Change one character to get `"hello"` |
| `"hell"` | `false` | Different length from `"hello"` |
| `"leetcoded"` | `false` | Different length from `"leetcode"` |

## First Thought: Compare Against Every Word

A direct solution is to store all dictionary words in a list.

When `search(searchWord)` is called, compare `searchWord` with every dictionary word of the same length.

For each candidate word, count how many positions differ.

If the number of differences is exactly `1`, return `true`.

Otherwise, keep checking.

```python
class MagicDictionary:

    def __init__(self):
        self.words = []

    def buildDict(self, dictionary: list[str]) -> None:
        self.words = dictionary

    def search(self, searchWord: str) -> bool:
        for word in self.words:
            if len(word) != len(searchWord):
                continue

            diff = 0

            for a, b in zip(word, searchWord):
                if a != b:
                    diff += 1

            if diff == 1:
                return True

        return False
```

This is easy to understand and valid.

## Problem With the Direct Solution

The direct solution may compare the query against many words.

If there are `n` words and each word has length `m`, then one search can take:

```text
O(n * m)
```

This may be acceptable for small input, but the data structure can be improved by precomputing patterns.

## Key Insight

Two words differ by exactly one character if they have the same length and become the same pattern after replacing one position with a wildcard.

For example:

```text
hello
```

Its wildcard patterns are:

```text
*ello
h*llo
he*lo
hel*o
hell*
```

Now consider:

```text
hhllo
```

Its wildcard patterns are:

```text
*hllo
h*llo
hh*lo
hhl*o
hhll*
```

Both `"hello"` and `"hhllo"` share this pattern:

```text
h*llo
```

That means they are the same except at the wildcard position.

So we can build a map from wildcard patterns to the original character that appeared at the wildcard position.

## Algorithm

During `buildDict`:

For every word in the dictionary:

1. Replace each character position with `'*'`.
2. Use the resulting pattern as a key.
3. Store the character that was replaced.

For example, for `"hello"`:

| Pattern | Replaced character |
|---|---|
| `"*ello"` | `'h'` |
| `"h*llo"` | `'e'` |
| `"he*lo"` | `'l'` |
| `"hel*o"` | `'l'` |
| `"hell*"` | `'o'` |

If the same pattern appears with different replaced characters, then any word with that pattern can match by changing one character.

To represent that, we can store a special marker such as `'*'`.

During `search`:

1. Generate every wildcard pattern of `searchWord`.
2. Look up the pattern.
3. If the stored character is different from the current character, return `true`.
4. Otherwise, continue.
5. Return `false` if no pattern works.

The condition “stored character is different from the current character” enforces exactly one changed character.

## Correctness

For any returned `true`, the algorithm found a wildcard pattern from `searchWord` that also exists in the built dictionary.

That means there is a dictionary word with the same length and the same characters at every position except the wildcard position.

The algorithm also checks that the replaced character differs from the search word’s character. Therefore, the dictionary word differs from `searchWord` by exactly one character.

For any valid match, suppose some dictionary word differs from `searchWord` by exactly one character at index `i`.

If we replace index `i` in both words with `'*'`, both words produce the same wildcard pattern.

This pattern was inserted during `buildDict`.

When `search` generates the same pattern, it finds the stored entry and sees that the character at index `i` is different. Therefore, the algorithm returns `true`.

So the algorithm returns `true` exactly when one character can be changed to form a dictionary word.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Number of dictionary words |
| `m` | Average word length |
| `q` | Length of `searchWord` |

For each word, we create one pattern per character. Creating a pattern by slicing costs `O(m)`.

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(1)` | `O(1)` |
| `buildDict` | `O(n * m^2)` | `O(n * m^2)` |
| `search` | `O(q^2)` | `O(q)` temporary pattern space |

The space can be described as the number of stored patterns times the pattern length.

## Implementation

```python
class MagicDictionary:

    def __init__(self):
        self.patterns = {}

    def buildDict(self, dictionary: list[str]) -> None:
        for word in dictionary:
            for i, ch in enumerate(word):
                pattern = word[:i] + "*" + word[i + 1:]

                if pattern in self.patterns:
                    self.patterns[pattern] = "*"
                else:
                    self.patterns[pattern] = ch

    def search(self, searchWord: str) -> bool:
        for i, ch in enumerate(searchWord):
            pattern = searchWord[:i] + "*" + searchWord[i + 1:]

            if self.patterns.get(pattern, ch) != ch:
                return True

        return False
```

## Code Explanation

The dictionary:

```python
self.patterns = {}
```

maps wildcard patterns to the character that was removed from the dictionary word.

For example:

```python
"hello" -> "h*llo"
```

stores:

```python
self.patterns["h*llo"] = "e"
```

If another dictionary word creates the same pattern, we set the value to `"*"`:

```python
if pattern in self.patterns:
    self.patterns[pattern] = "*"
```

This means the pattern can be formed from multiple words, possibly with different characters at the replaced position.

In `search`, we generate the same kind of wildcard pattern:

```python
pattern = searchWord[:i] + "*" + searchWord[i + 1:]
```

Then we check:

```python
if self.patterns.get(pattern, ch) != ch:
    return True
```

This line has two cases.

If the pattern does not exist, `get(pattern, ch)` returns `ch`, so the condition is false.

If the pattern exists with the same character, that means the word may be identical at this position, so it does not prove exactly one change.

If the pattern exists with a different character, then replacing the current character can produce a dictionary word.

The marker `"*"` is also different from any lowercase letter, so it correctly returns `true` when multiple dictionary words share the same pattern.

## Testing

```python
def run_tests():
    obj = MagicDictionary()
    obj.buildDict(["hello", "leetcode"])

    assert obj.search("hello") is False
    assert obj.search("hhllo") is True
    assert obj.search("hell") is False
    assert obj.search("leetcoded") is False

    obj = MagicDictionary()
    obj.buildDict(["hello", "hallo"])

    assert obj.search("hello") is True
    assert obj.search("hhllo") is True
    assert obj.search("hella") is True

    obj = MagicDictionary()
    obj.buildDict(["a", "b"])

    assert obj.search("a") is True
    assert obj.search("c") is True
    assert obj.search("aa") is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `search("hello")` after `["hello", "leetcode"]` | `false` | Exact same word needs zero changes |
| `search("hhllo")` | `true` | One replacement gives `"hello"` |
| `search("hell")` | `false` | Replacement cannot change length |
| `search("leetcoded")` | `false` | Replacement cannot remove a character |
| Dictionary `["hello", "hallo"]`, search `"hello"` | `true` | Change `'e'` to `'a'` to get `"hallo"` |
| Dictionary `["a", "b"]`, search `"a"` | `true` | Change `'a'` to `'b'` |
| Dictionary `["a", "b"]`, search `"aa"` | `false` | No same-length dictionary word |