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

Function shape:

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

Examples

Example 1:

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

"mee" matches "abb":

The mapping is consistent.

"aqq" also matches "abb":

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

Example 2:

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

a -> m
b -> e

This seems enough at first.

But consider:

word = "ccc"
pattern = "abb"

A one-direction map gives:

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:

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:

word = "mee"
pattern = "abb"

Start with empty maps:

p_to_w = {}
w_to_p = {}

Step 1:

Step 2:

Step 3:

No conflict, so "mee" matches.

Now check:

word = "ccc"
pattern = "abb"

Step 1:

Step 2:

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:

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

Implementation

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:

def matches(word: str) -> bool:

We create two maps:

p_to_w = {}
w_to_p = {}

Then we scan the pattern and word together:

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

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

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:

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

Otherwise, we record the mapping:

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

If all character pairs pass, the word matches.

Finally, we filter all words:

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

Testing

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: