Find and Replace Pattern: Bijection Mapping

LeetCode 890, Find and Replace Pattern, gives you a list of words and a pattern string. Your job is to return every word that matches the pattern. Two strings "match" when there is a one-to-one mapping (a bijection) between the characters of the pattern and the characters of the word. If you have already solved Word Pattern or Isomorphic Strings, this problem uses the exact same core technique. The twist is that you apply it to a list of words and collect the ones that pass.

Why a single map is not enough

Imagine you only keep a forward map from pattern characters to word characters. Pattern "ab" and word "aa" would proceed like this: map a -> a at index 0, then try to map b -> a at index 1. The forward map has no entry for b yet, so it happily records b -> a. The single map says the word matches, but it should not. Two different pattern characters (a and b) are both pointing to the same word character (a). That violates the one-to-one requirement.

The fix is a second map going the other direction: from word characters back to pattern characters. When you try to record a -> b in the backward map, you find that a is already mapped to pattern char a. Conflict. The backward map catches the problem immediately.

This is the bijection pattern. One map ensures that each pattern character maps to a consistent word character. The other map ensures that each word character maps back to a consistent pattern character. Together, they enforce the one-to-one correspondence.

Approach: two hash maps for bijection

For each word, walk through both strings in lockstep. Maintain two dictionaries: p_to_w (pattern to word) and w_to_p (word to pattern). At each position, check both maps for conflicts. If you make it through the entire word without a conflict, the word matches.

def findAndReplacePattern(words: list[str], pattern: str) -> list[str]:
    def matches(word: str) -> bool:
        if len(word) != len(pattern):
            return False
        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 [w for w in words if matches(w)]

Alternative: normalize to canonical form

Instead of checking bijection with two maps, you can convert both the pattern and each word into a canonical form. The idea: replace the first new character you see with 0, the second new character with 1, and so on. If both strings produce the same sequence of integers, they have the same structure.

For example, "abb" becomes [0, 1, 1]. "mee" also becomes [0, 1, 1]. They match. "abc" becomes [0, 1, 2], which does not match [0, 1, 1].

def findAndReplacePattern(words: list[str], pattern: str) -> list[str]:
    def normalize(s: str) -> list[int]:
        mapping = {}
        result = []
        for ch in s:
            if ch not in mapping:
                mapping[ch] = len(mapping)
            result.append(mapping[ch])
        return result

    target = normalize(pattern)
    return [w for w in words if normalize(w) == target]

This approach is arguably cleaner to write and reason about. It sidesteps the two-map logic entirely. The tradeoff is that you build the normalized form for every word, but the cost is the same O(k) per word either way.

Step-by-step walkthrough

Complexity analysis

Where n is the number of words and k is the length of each word (all words have the same length as the pattern in this problem). Both approaches iterate through each word once, doing O(1) work per character. The space per word is O(k) for the maps or the normalized list, but you reset it for each word, so the peak usage is O(k).

Building blocks

1. Bijection verification with two maps

The bidirectional hash map check is a reusable template. One map alone verifies that each key maps to a consistent value, but it cannot prevent two different keys from mapping to the same value. The second map enforces that constraint. Any time a problem asks for a one-to-one correspondence, consistent substitution, or structural equivalence, this is the tool.

forward = {}
backward = {}
for a, b in zip(seq1, seq2):
    if a in forward and forward[a] != b:
        return False
    if b in backward and backward[b] != a:
        return False
    forward[a] = b
    backward[b] = a
return True

2. String normalization

Converting a string to its canonical form (replacing the first unique character with 0, the next with 1, and so on) is the same technique used in Isomorphic Strings. It transforms the question from "do these two strings have the same structure?" into "do these two strings produce the same integer sequence?" Equality checks on lists are fast and simple.

Edge cases

• All characters the same. Pattern "aaa" with word "zzz" is a valid match. The single mapping a -> z is consistent throughout. But "aaa" with "zzy" fails because a would need to map to both z and y.
• Pattern is the identity. Pattern "abc" requires every character in the word to be distinct. "mno" matches, "mmo" does not.
• Single character. Pattern "a" matches any single-character word. There is only one pair, and a single mapping is always consistent.

From understanding to recall

Find and Replace Pattern is a direct application of the bijection technique you see in Isomorphic Strings and Word Pattern. The code is short, and once you see the two-map trick, the solution feels obvious. But the real value is internalizing when to reach for it. Any time a problem says "consistent mapping," "one-to-one correspondence," or "same structure," the two-map template should fire automatically. Spaced repetition helps you build that reflex. You practice the pattern from scratch at increasing intervals until the recognition is instant and the code flows from memory.

Related posts

• Isomorphic Strings - The same bijection pattern applied to two strings
• Word Pattern - Bijection between words and characters
• Group Anagrams - Another pattern-matching hash map problem