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:

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

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:

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:

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:

word = "mee"
pattern = "abb"

Start with empty maps:

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:

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:

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

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:

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