Find and Replace Pattern

medium hash map bijection string

Problem

Given a list of words and a pattern, return the words that match the pattern. A word matches if there is a bijection (one-to-one mapping) of letters that turns the pattern into the word — every pattern letter maps to exactly one word letter and no two pattern letters map to the same word letter.

Inputwords = [abc, deq, mee, aqq], pattern = abb

Output[mee, aqq]

For "mee", a→m and b→e is a valid bijection. "abc" fails because pattern's repeated b would need two different word letters.

words (comma-separated)

pattern

def find_and_replace_pattern(words, pattern):
    def matches(word):
        p2w, w2p = {}, {}
        for p, w in zip(pattern, word):
            if p2w.setdefault(p, w) != w:
                return False
            if w2p.setdefault(w, p) != p:
                return False
        return True
    return [w for w in words if len(w) == len(pattern) and matches(w)]

function findAndReplacePattern(words, pattern) {
  function matches(word) {
    const p2w = new Map(), w2p = new Map();
    for (let i = 0; i < pattern.length; i++) {
      const p = pattern[i], w = word[i];
      if (p2w.has(p) && p2w.get(p) !== w) return false;
      if (w2p.has(w) && w2p.get(w) !== p) return false;
      p2w.set(p, w); w2p.set(w, p);
    }
    return true;
  }
  return words.filter(w => w.length === pattern.length && matches(w));
}

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res = new ArrayList<>();
        for (String w : words) if (matches(w, pattern)) res.add(w);
        return res;
    }
    private boolean matches(String word, String pattern) {
        if (word.length() != pattern.length()) return false;
        Map<Character, Character> p2w = new HashMap<>(), w2p = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char p = pattern.charAt(i), w = word.charAt(i);
            if (p2w.containsKey(p) && p2w.get(p) != w) return false;
            if (w2p.containsKey(w) && w2p.get(w) != p) return false;
            p2w.put(p, w); w2p.put(w, p);
        }
        return true;
    }
}

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> res;
        for (auto& w : words) if (matches(w, pattern)) res.push_back(w);
        return res;
    }
    bool matches(const string& word, const string& pattern) {
        if (word.size() != pattern.size()) return false;
        unordered_map<char, char> p2w, w2p;
        for (int i = 0; i < (int)pattern.size(); i++) {
            char p = pattern[i], w = word[i];
            if (p2w.count(p) && p2w[p] != w) return false;
            if (w2p.count(w) && w2p[w] != p) return false;
            p2w[p] = w; w2p[w] = p;
        }
        return true;
    }
};

Explanation

A word matches the pattern when you can consistently rename the pattern's letters into the word's letters. The catch is the renaming must be one-to-one in both directions, so we track two maps, not one.

We walk the pattern and word together, character by character. p2w remembers what each pattern letter maps to, and w2p remembers what each word letter maps back to. At every position we check that the current pair agrees with whatever was recorded before.

Why two maps? One map alone would allow two different pattern letters to both map to the same word letter, which breaks the one-to-one rule. The reverse map w2p catches that collision. If either map ever conflicts, the word fails.

Example: pattern abb against mee. We map a→m, then b→e, then the second b must also be e, which holds, so mee matches. But abc fails: the pattern's repeated b would need two different word letters (b then c).

Running this filter over every word collects the matches, here [mee, aqq].

Time: O(n · m) Space: O(m)