Problem

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 xin the pattern with p(x), we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Examples

Example 1:

1
2
3
4
5
6

Input:
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output:
 ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.

Example 2:

1
2
3
4

Input:
words = ["a","b","c"], pattern = "a"
Output:
 ["a","b","c"]

Solution

Method 1 – Double Hash Mapping

Intuition

The key idea is to check if each word can be mapped to the pattern using a bijection (one-to-one mapping) between characters. We use two hash maps: one from pattern to word and one from word to pattern, ensuring that each character maps uniquely in both directions. If at any position the mapping is inconsistent, the word does not match the pattern.

Approach

  1. For each word in words, check if it matches the pattern:
    • Use two hash maps: p2w (pattern to word) and w2p (word to pattern).
    • For each character position, if the mapping is not set, set it; if set, check for consistency.
    • If all positions are consistent, add the word to the answer.
  2. Return the list of matching words.

Complexity

  • ⏰ Time complexity: O(N * L), where N is the number of words and L is the length of each word.
  • 🧺 Space complexity: O(L), for the hash maps per word.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> ans;
        for (const string& word : words) {
            unordered_map<char, char> p2w, w2p;
            bool match = true;
            for (int i = 0; i < word.size(); ++i) {
                char p = pattern[i], w = word[i];
                if (p2w.count(p) && p2w[p] != w) { match = false; break; }
                if (w2p.count(w) && w2p[w] != p) { match = false; break; }
                p2w[p] = w;
                w2p[w] = p;
            }
            if (match) ans.push_back(word);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        for (String word : words) {
            Map<Character, Character> p2w = new HashMap<>();
            Map<Character, Character> w2p = new HashMap<>();
            boolean match = true;
            for (int i = 0; i < word.length(); i++) {
                char p = pattern.charAt(i), w = word.charAt(i);
                if (p2w.containsKey(p) && p2w.get(p) != w) { match = false; break; }
                if (w2p.containsKey(w) && w2p.get(w) != p) { match = false; break; }
                p2w.put(p, w);
                w2p.put(w, p);
            }
            if (match) ans.add(word);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findAndReplacePattern(self, words: list[str], pattern: str) -> list[str]:
        ans = []
        for word in words:
            p2w, w2p = {}, {}
            match = True
            for pc, wc in zip(pattern, word):
                if pc in p2w and p2w[pc] != wc:
                    match = False
                    break
                if wc in w2p and w2p[wc] != pc:
                    match = False
                    break
                p2w[pc] = wc
                w2p[wc] = pc
            if match:
                ans.append(word)
        return ans