Problem Description

Given a list of strings words and a string pattern, return a list of all words in words that match the same pattern as pattern.
A word matches the pattern if there is a bijection (one-to-one and onto mapping) between every character in the pattern and every character in the word. In other words, replacing each letter in the pattern with a unique letter from the word yields the word itself, and no two characters in the pattern map to the same character in the word.
Key constraints:

• Each character in pattern must map to exactly one character in the word.
• No two different characters in pattern can map to the same character in the word.
• All words and the pattern are of the same length.

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

Thought Process

At first glance, you might think of comparing each word to the pattern character by character, but that doesn't account for the bijection requirement. For example, the pattern "abb" should only match words where the first character is unique and the last two characters are the same, and the mapping from pattern to word is consistent and unique.
A brute-force approach would try all possible mappings for each word, but that's inefficient. Instead, we can think in terms of encoding the "structure" of the pattern and each word. If two strings have the same structural encoding, they match.
For example, "abb" encodes as [0,1,1] (first letter is unique, next two are the same). If a word encodes the same way, it's a match. This reduces the problem to pattern matching by structure, not by specific characters.

Solution Approach

To solve this efficiently, we use the following approach:

1. Encode the pattern: Create a helper function that encodes a string by mapping each unique character to an integer in the order of its appearance. For example, "abb" becomes [0,1,1], "mee" becomes [0,1,1], and "abc" becomes [0,1,2].
2. Compare encodings: For each word in words, encode it using the same function and compare its encoding to that of pattern.
3. Collect matches: If a word's encoding matches the pattern's encoding, add it to the result list.

• We use a hash map (dictionary) to assign each character an index as we encounter it, ensuring O(1) lookups and consistent mapping.
• This approach avoids nested loops and backtracking, making it efficient and easy to implement.

Example Walkthrough

Given: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Step 1: Encode the pattern "abb":
- 'a' → 0
- 'b' → 1
- next 'b' → 1
So, encoding = [0,1,1]

Step 2: Encode each word and compare:

• "abc": ['a'→0, 'b'→1, 'c'→2] → [0,1,2] ≠ [0,1,1] (no match)
• "deq": ['d'→0, 'e'→1, 'q'→2] → [0,1,2] ≠ [0,1,1] (no match)
• "mee": ['m'→0, 'e'→1, next 'e'→1] → [0,1,1] = [0,1,1] (match)
• "aqq": ['a'→0, 'q'→1, next 'q'→1] → [0,1,1] = [0,1,1] (match)
• "dkd": ['d'→0, 'k'→1, 'd'→0] → [0,1,0] ≠ [0,1,1] (no match)
• "ccc": ['c'→0, next 'c'→0, next 'c'→0] → [0,0,0] ≠ [0,1,1] (no match)

Time and Space Complexity

Brute-force approach:

• Would involve generating all possible mappings between pattern and word characters, leading to factorial time complexity with respect to word length (O(n!)).

• Let n be the number of words, and k be the length of each word (and pattern).
• Encoding each word and the pattern takes O(k) time.
• We check each of the n words, so total time is O(nk).
• Space complexity is O(k) for the encoding of each word, which is reused, and O(nk) for the result list in the worst case (if all words match).

Summary

The key insight is to reduce the problem to comparing the "structure" of the pattern and each word using an encoding function. By encoding both as lists of indices representing the first occurrence of each character, we efficiently check for a one-to-one mapping (bijection) without complex backtracking or brute-force mapping. This approach is elegant, concise, and leverages hash maps for efficient lookups, making it suitable for large inputs and easy to implement in any language.

Code Implementation

class Solution:
    def findAndReplacePattern(self, words, pattern):
        def encode(s):
            mapping = {}
            code = []
            i = 0
            for ch in s:
                if ch not in mapping:
                    mapping[ch] = i
                    i += 1
                code.append(mapping[ch])
            return code

        pattern_code = encode(pattern)
        return [word for word in words if encode(word) == pattern_code]
      

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<int> encode(const string& s) {
            unordered_map<char, int> mapping;
            vector<int> code;
            int i = 0;
            for (char ch : s) {
                if (!mapping.count(ch)) {
                    mapping[ch] = i++;
                }
                code.push_back(mapping[ch]);
            }
            return code;
        }
        vector<int> pattern_code = encode(pattern);
        vector<string> res;
        for (const string& word : words) {
            if (encode(word) == pattern_code)
                res.push_back(word);
        }
        return res;
    }
};
      

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> res = new ArrayList<>();
        int[] patternCode = encode(pattern);
        for (String word : words) {
            if (Arrays.equals(encode(word), patternCode))
                res.add(word);
        }
        return res;
    }
    
    private int[] encode(String s) {
        Map<Character, Integer> mapping = new HashMap<>();
        int[] code = new int[s.length()];
        int idx = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!mapping.containsKey(ch)) {
                mapping.put(ch, idx++);
            }
            code[i] = mapping.get(ch);
        }
        return code;
    }
}
      

var findAndReplacePattern = function(words, pattern) {
    function encode(s) {
        let mapping = {};
        let code = [];
        let i = 0;
        for (let ch of s) {
            if (!(ch in mapping)) {
                mapping[ch] = i++;
            }
            code.push(mapping[ch]);
        }
        return code.join(',');
    }
    let patternCode = encode(pattern);
    return words.filter(word => encode(word) === patternCode);
};