Find and Replace Pattern

Medium
638.

Find and Replace Pattern

Find and Replace Pattern is a medium coding problem on strings and hash table, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} pattern
 * @return {string[]}
 */
var findAndReplacePattern = function(words, pattern) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find and Replace Pattern — Solution in Python, Java & C++

Find and Replace Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find and Replace Pattern is a medium coding problem on strings and hash table, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find and Replace Pattern

  1. Hint 1

    One map is not enough — "abc" would 'match' "aaa" if you only check one direction.

  2. Hint 2

    Keep two maps: pattern letter to word letter and word letter back to pattern letter.

  3. Hint 3

    A contradiction in either direction rejects the word immediately.

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)]

Java

public static String[] findAndReplacePattern(String[] words, String pattern) {
    List<String> out = new ArrayList<>();
    for (String w : words) {
        if (w.length() != pattern.length()) continue;
        int[] fwd = new int[128];
        int[] back = new int[128];
        boolean ok = true;
        for (int i = 0; i < w.length(); i++) {
            char a = w.charAt(i), b = pattern.charAt(i);
            if (fwd[a] == 0) fwd[a] = b;
            else if (fwd[a] != b) { ok = false; break; }
            if (back[b] == 0) back[b] = a;
            else if (back[b] != a) { ok = false; break; }
        }
        if (ok) out.add(w);
    }
    return out.toArray(new String[0]);
}

C++

vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
    vector<string> out;
    for (const string& w : words) {
        if (w.size() != pattern.size()) continue;
        vector<char> fwd(128, 0), back(128, 0);
        bool ok = true;
        for (size_t i = 0; i < w.size(); i++) {
            char a = w[i], b = pattern[i];
            if (!fwd[(int) a]) fwd[(int) a] = b;
            else if (fwd[(int) a] != b) { ok = false; break; }
            if (!back[(int) b]) back[(int) b] = a;
            else if (back[(int) b] != a) { ok = false; break; }
        }
        if (ok) out.push_back(w);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets