890 - Find and Replace Pattern

Difficulty: Medium | Pattern: HashMap (Isomorphism) | Company tags: Amazon, Google, Facebook

Problem Statement

Given a list of strings words and a string pattern, return a list of words[i] that match pattern. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

Example:

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

Approach: Isomorphism Check — O(n × L)

Key insight: Two strings are isomorphic if their character mappings are consistent in both directions. Use two dicts to check word → pattern and pattern → word mapping.

def findAndReplacePattern(words: list[str], pattern: str) -> list[str]:
    def matches(word):
        if len(word) != len(pattern):
            return False
        w_to_p = {}
        p_to_w = {}
        for w, p in zip(word, pattern):
            if w_to_p.get(w, p) != p or p_to_w.get(p, w) != w:
                return False
            w_to_p[w] = p
            p_to_w[p] = w
        return True
    
    return [w for w in words if matches(w)]

Algorithm Flow

Alternative: Normalize to Indices

Encode both word and pattern as their character-index sequence and compare:

def encode(s):
    mapping = {}
    return [mapping.setdefault(c, len(mapping)) for c in s]

def findAndReplacePattern(words, pattern):
    p = encode(pattern)
    return [w for w in words if encode(w) == p]

Dry Run

pattern = "abb", word = "mee"

w	p	w_to_p	p_to_w	ok?
m	a	m→a	a→m	yes
e	b	m→a, e→b	a→m, b→e	yes
e	b	consistent	consistent	yes

→ match ✓

word = "abc": a→a,b→b,c→c but pattern is "abb" so a→a,b→b,c→b → 'c' maps to 'b' but 'b' already maps to something else → no match ✓

Complexity

• Time: O(n × L)
• Space: O(L) per word check

Key Terms

Term	Definition
Isomorphism	Two sequences share the same underlying structure when there's a consistent one-to-one character mapping between them.
Bijective mapping	A mapping that is both a function and injective — each character in one string maps to exactly one character in the other, and vice versa.
Pattern normalization	Encoding a string as the sequence of first-occurrence indices of its characters, making structurally identical strings compare equal.
Two-way hashmap check	Using both word → pattern and pattern → word dictionaries to enforce a strict bijection instead of a one-directional mapping.

FAQ

1. Can this be solved without extra space? Not really below O(L) — you need at least one mapping structure to track character correspondence per word being checked; the encoding approach also uses O(L) auxiliary space.
2. What if words is empty? The list comprehension iterates zero times and returns an empty list — no special-casing needed.
3. Why check both w_to_p and p_to_w instead of just one direction? A single direction only proves a function exists (word → pattern), not that it's a bijection. E.g., pattern "abb" could otherwise wrongly match "xyy" being checked against "aab" style collisions if only one direction is validated — both maps prevent two different pattern letters from mapping to the same word letter and vice versa.
4. What if the constraint required case-insensitive matching? Lowercase (or uppercase) both word and pattern before building the maps; the same isomorphism logic applies unchanged.
5. What's the common follow-up interviewers ask? "Solve Isomorphic Strings (LC 205)," which is the same two-way mapping check applied to exactly one pair of strings instead of filtering a list.

Quick Revision

• Pattern: HashMap-based isomorphism / bijective character mapping.
• A word matches if there's a permutation p such that applying p to pattern yields the word.
• Maintain two dicts: w_to_p and p_to_w, updated in lockstep as you scan both strings together.
• Reject early if either mapping direction is violated or lengths differ.
• Alternative: normalize both strings to "first-occurrence index" encodings and compare directly.
• Time: O(n × L) where n = number of words, L = pattern length.
• Space: O(L) per word check (or O(1) extra if reusing structures carefully).
• Edge cases: empty words list, single-character pattern, all-identical characters in pattern.

Related Problems

• 205 - Isomorphic Strings — the exact same bijective mapping check applied to a single pair of strings.
• 242 - Valid Anagram — related hashmap character-frequency technique, though it checks multiset equality rather than structural mapping.
• Word Pattern (LeetCode 290) — same isomorphism idea applied between a pattern string and a sequence of words.