# LeetCode 890: Find and Replace Pattern

## Problem Restatement

We are given a list of strings `words` and a string `pattern`.

We need to return all words that match the pattern.

A word matches the pattern if there is a bijection between letters in `pattern` and letters in the word. That means:

1. Each pattern character maps to exactly one word character.
2. No two pattern characters map to the same word character.
3. The mapping must be consistent across the whole word.

The answer can be returned in any order. LeetCode defines the mapping as a permutation, meaning every letter maps to another letter and no two letters map to the same letter.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `words`, a list of lowercase strings |
| Input | `pattern`, a lowercase string |
| Output | Words that match `pattern` |
| Word length | Every `words[i]` has the same length as `pattern` |
| Order | Any order is accepted |

Function shape:

```python
def findAndReplacePattern(self, words: list[str], pattern: str) -> list[str]:
    ...
```

## Examples

Example 1:

```text
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
```

`"mee"` matches `"abb"`:

| Pattern | Word |
|---|---|
| `a` | `m` |
| `b` | `e` |
| `b` | `e` |

The mapping is consistent.

`"aqq"` also matches `"abb"`:

| Pattern | Word |
|---|---|
| `a` | `a` |
| `b` | `q` |
| `b` | `q` |

`"ccc"` does not match `"abb"` because both `a` and `b` would need to map to `c`, which violates the bijection rule.

Example 2:

```text
Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]
```

Every one-letter word matches a one-letter pattern.

## First Thought: One Direction Map

A first idea is to map each pattern character to the corresponding word character.

For example, checking `"mee"` against `"abb"`:

```text
a -> m
b -> e
```

This seems enough at first.

But consider:

```text
word = "ccc"
pattern = "abb"
```

A one-direction map gives:

```text
a -> c
b -> c
```

Each pattern character maps consistently, but two different pattern characters map to the same word character.

That is invalid.

So we need a two-way mapping.

## Key Insight

The mapping must be bijective.

So while checking a word against the pattern, we maintain:

| Map | Meaning |
|---|---|
| `p_to_w` | Pattern character to word character |
| `w_to_p` | Word character to pattern character |

For each aligned pair `(p, w)`:

1. If `p` was already mapped, it must map to `w`.
2. If `w` was already mapped, it must map from `p`.
3. Otherwise, create both mappings.

If any check fails, the word does not match.

## Algorithm

For each word in `words`:

1. Create two empty hash maps.
2. Compare the word and `pattern` character by character.
3. For each pair `(p, w)`:
   1. Check whether `p` already maps to a different `w`.
   2. Check whether `w` already maps to a different `p`.
   3. If either check fails, reject the word.
   4. Otherwise, store both mappings.
4. If the whole word passes, add it to the answer.

Return the answer.

## Walkthrough

Check:

```text
word = "mee"
pattern = "abb"
```

Start with empty maps:

```text
p_to_w = {}
w_to_p = {}
```

Step 1:

| Pattern | Word | Action |
|---|---|---|
| `a` | `m` | Add `a -> m` and `m -> a` |

Step 2:

| Pattern | Word | Action |
|---|---|---|
| `b` | `e` | Add `b -> e` and `e -> b` |

Step 3:

| Pattern | Word | Action |
|---|---|---|
| `b` | `e` | Existing mapping matches |

No conflict, so `"mee"` matches.

Now check:

```text
word = "ccc"
pattern = "abb"
```

Step 1:

| Pattern | Word | Action |
|---|---|---|
| `a` | `c` | Add `a -> c` and `c -> a` |

Step 2:

| Pattern | Word | Problem |
|---|---|---|
| `b` | `c` | `c` already maps back to `a` |

So `"ccc"` does not match.

## Correctness

The algorithm accepts a word only if every aligned character pair satisfies both mapping directions.

If a pattern character appears more than once, the `p_to_w` map ensures it always maps to the same word character.

If a word character appears more than once, the `w_to_p` map ensures it always comes from the same pattern character.

Therefore, no pattern character maps to two different word characters, and no two pattern characters map to the same word character.

This is exactly the bijection required by the problem.

If a valid bijection exists, then every aligned pair is consistent in both directions. The algorithm will never detect a conflict, so it will accept the word.

If the algorithm accepts the word, the two maps define a valid bijection between the characters used in the pattern and the characters used in the word. Therefore, replacing each pattern character according to this mapping produces the word.

Thus, the algorithm returns exactly the words that match the pattern.

## Complexity

Let:

```text
m = len(words)
L = len(pattern)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * L)` | We check each character of each word |
| Space | `O(L)` | The maps store at most one entry per distinct character in a word or pattern |

## Implementation

```python
class Solution:
    def findAndReplacePattern(self, words: list[str], pattern: str) -> list[str]:
        def matches(word: str) -> bool:
            p_to_w = {}
            w_to_p = {}

            for p, w in zip(pattern, word):
                if p in p_to_w and p_to_w[p] != w:
                    return False

                if w in w_to_p and w_to_p[w] != p:
                    return False

                p_to_w[p] = w
                w_to_p[w] = p

            return True

        return [word for word in words if matches(word)]
```

## Code Explanation

The helper function checks one word:

```python
def matches(word: str) -> bool:
```

We create two maps:

```python
p_to_w = {}
w_to_p = {}
```

Then we scan the pattern and word together:

```python
for p, w in zip(pattern, word):
```

If `p` already maps to another character, the word is invalid:

```python
if p in p_to_w and p_to_w[p] != w:
    return False
```

If `w` already maps back to another pattern character, the word is invalid:

```python
if w in w_to_p and w_to_p[w] != p:
    return False
```

Otherwise, we record the mapping:

```python
p_to_w[p] = w
w_to_p[w] = p
```

If all character pairs pass, the word matches.

Finally, we filter all words:

```python
return [word for word in words if matches(word)]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert sorted(s.findAndReplacePattern(
        ["abc", "deq", "mee", "aqq", "dkd", "ccc"],
        "abb"
    )) == ["aqq", "mee"]

    assert sorted(s.findAndReplacePattern(
        ["a", "b", "c"],
        "a"
    )) == ["a", "b", "c"]

    assert s.findAndReplacePattern(
        ["ccc"],
        "abb"
    ) == []

    assert s.findAndReplacePattern(
        ["abc"],
        "aaa"
    ) == []

    assert s.findAndReplacePattern(
        ["xyy", "yxx", "abc"],
        "abb"
    ) == ["xyy", "yxx"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Finds only words with pattern shape `abb` |
| One-letter pattern | Every one-letter word matches |
| Many pattern chars mapping to one word char | Rejects non-bijection |
| One pattern char mapping to many word chars | Rejects inconsistent mapping |
| Multiple valid words | Accepts any valid bijection |