Find and Replace Pattern — Medium Problem & Solution

Problem statement

A word matches a pattern when there is a one-to-one letter substitution turning the pattern into the word — every pattern letter always maps to the same word letter, and no two pattern letters map to the same word letter.

Return every word in words that matches pattern, keeping the original order.

Example 1

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" works with a->m and b->e; "dkd" fails because the pattern needs b->k and b->d at once.

Example 2

Input: words = ["kata","duel","rank"], pattern = "abcd"
Output: ["duel","rank"]
Explanation: "kata" repeats a, which "abcd" does not.

Example 3

Input: words = ["aa","bb","ab"], pattern = "cc"
Output: ["aa","bb"]

Constraints

• 1 <= pattern.length <= 20
• 1 <= words.length <= 50
• words[i].length == pattern.length
• All strings consist of lowercase English letters.

How to solve Find and Replace Pattern

A one-to-one substitution is a bijection, and a bijection is exactly two consistent maps — one in each direction. Checking both is what rules out two pattern letters collapsing onto the same word letter.

Approach

1. For each word, walk the positions with two empty maps.
2. At position i, bind word[i] -> pattern[i] and pattern[i] -> word[i], rejecting the word if either binding contradicts an existing one.
3. Keep the word if the walk finishes without a contradiction.

Why it works

The forward map enforces that a pattern letter never maps to two different word letters; the backward map enforces injectivity, so two pattern letters can never share a word letter. Together they are precisely the definition of a permutation of the alphabet restricted to the letters used.

Complexity

• Time — O(n · m) for n words of length m
• Space — O(1) — at most 26 entries per map

Pitfalls

• Checking only one direction accepts "aaa" for pattern "abc".
• Reusing the maps between words leaks bindings from the previous word.

Reference solution

Python

from typing import List

def findAndReplacePattern(words: List[str], pattern: str) -> List[str]:
    def ok(w: str) -> bool:
        fwd, back = {}, {}
        for a, b in zip(w, pattern):
            if fwd.setdefault(a, b) != b:
                return False
            if back.setdefault(b, a) != a:
                return False
        return True
    return [w for w in words if ok(w)]

JavaScript

var findAndReplacePattern = function(words, pattern) {
    var ok = function(w) {
        if (w.length !== pattern.length) return false;
        var fwd = {}, back = {};
        for (var i = 0; i < w.length; i++) {
            var a = w.charAt(i), b = pattern.charAt(i);
            if (fwd[a] === undefined) fwd[a] = b;
            else if (fwd[a] !== b) return false;
            if (back[b] === undefined) back[b] = a;
            else if (back[b] !== a) return false;
        }
        return true;
    };
    var out = [];
    for (var j = 0; j < words.length; j++) {
        if (ok(words[j])) out.push(words[j]);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium