Problem Description

Given a list of words and a pattern, we need to find out which words in the list match the given pattern.

The word is considered to match the pattern if there exists a bijective mapping (permutation) between the characters of the pattern and the characters of the word. In such mapping, each character in the pattern can map to a character in the word, and no two characters in the pattern can map to the same character in the word.

We need to return a list of the words that match the pattern. The order of the words does not matter.

Example

Given the words list as ["abc","deq","mee","aqq","dkd","ccc"] and the pattern as "abb". The output should be ["mee","aqq"].

The word "mee" matches the pattern because there exists a permutation {a -> m, b -> e}. However, the word "ccc" doesn't match as the permutation {a -> c, b -> c} is not a valid permutation since 'a' and 'b' both map to 'c'.

Solution

To solve the problem, the solution is to iterate over each word in the list and for each word, we build two mapping arrays(one for word and other for pattern). If at any character position 'i', the character at 'i' in word doesn't map to the same character as the character at 'i' in pattern, then this word doesn't match the pattern. We increment the mapping values for each character with 'i+1' so that 0 mappings are differentiated from yet to be mapped characters.

Python Solution

1
2python
3class Solution:
4    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
5        def match(word):
6            map_p = {}
7            map_w = {}
8            for p, w in zip(pattern, word):
9                if map_p.setdefault(p, w) != w or map_w.setdefault(w, p) != p:
10                    return False
11            return True
12
13        return [word for word in words if match(word)]

Java Solution

1
2java
3class Solution {
4    public List<String> findAndReplacePattern(String[] words, String pattern) {
5        List<String> ans = new ArrayList<>();
6        for (String word : words)
7            if (match(word, pattern))
8                ans.add(word);
9        return ans;
10    }
11
12    public boolean match(String word, String pattern) {
13        int[] map_p = new int[128];
14        int[] map_w = new int[128];
15        for(int i = 0; i < word.length(); i++){
16            if(map_p[word.charAt(i)] != map_w[pattern.charAt(i)]) return false;
17            map_p[word.charAt(i)] = i+1;
18            map_w[pattern.charAt(i)] = i+1;
19        }
20        return true;
21    }
22}

Javascript Solution

1
2javascript
3var findAndReplacePattern = function(words, pattern) {
4    var ans = [];
5    for(let word of words){
6        if(isIsomorphic(word, pattern)){
7            ans.push(word);
8        }
9    }
10
11    return ans;
12};
13
14function isIsomorphic(word, pattern){
15    let map_w = new Array(128).fill(0);
16    let map_p = new Array(128).fill(0);
17
18    for (let i = 0; i < word.length; ++i) {
19        if (map_w[word.charCodeAt(i)] != map_p[pattern.charCodeAt(i)])
20            return false;
21        map_w[word.charCodeAt(i)] = i + 1;
22        map_p[pattern.charCodeAt(i)] = i + 1;
23    }
24
25    return true;
26}

C++ Solution

1
2cpp
3class Solution {
4public:
5  vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
6    vector<string> ans;
7    for (const string& word : words)
8      if (isIsomorphic(word, pattern))
9        ans.push_back(word);
10    return ans;
11  }
12
13private:
14  bool isIsomorphic(const string& w, const string& p) {
15    vector<int> map_w(128), map_p(128);
16
17    for (int i = 0; i < w.length(); i++) {
18      if (map_w[w[i]] != map_p[p[i]]) return false;
19      map_w[w[i]] = i + 1;
20      map_p[p[i]] = i + 1;
21    }
22    return true;
23  }
24};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> FindAndReplacePattern(string[] words, string pattern) {
5        var ans = new List<string>();
6        foreach (var word in words) {
7            if (IsIsomorphic(word, pattern)) {
8                ans.Add(word);
9            }
10        }
11        return ans;
12    }
13
14    private bool IsIsomorphic(string word, string pattern) {
15        var mapW = new int[128];
16        var mapP = new int[128];
17        for (var i = 0; i < word.Length; ++i) {
18            if (mapW[word[i]] != mapP[pattern[i]]) {
19                return false;
20            }
21            mapW[word[i]] = i + 1;
22            mapP[pattern[i]] = i + 1;
23        }
24        return true;
25    }
26}

Explanation

Our task is to match each word from the words list to a specified pattern. This is done by iterating through each word and character of that word. For each character, we create a mapping that allows us to ensure that the same character mapping doesn't exist beforehand. Suppose this mapping exists, we know that the word doesn't match the pattern.

This task is achieved using various string manipulation functions available in Python, Java, JavaScript, C++, and C#. Essentially, the logic remains the same. We maintain two mapping arrays for realizing a bijective relationship between the character mappings. If the mappings don't match, we can quickly determine that the word does not match the pattern.

The Bijective relationship ensures that each character in the input word should map completely and precisely to a character in the pattern, with no character repetition. For instance, two different letters in the pattern should not map to the same character in the word.

The beauty of this algorithm is its simplicity and intuitive nature, both of which contribute to the overall time complexity of the algorithm, making it run in linear time and constant space. This clever usage of extra auxiliary mapping space helps us identify the non-matching words quickly and thereby increases the overall speed of the solution.

Remember, in the end, we return a list/array of words that match the pattern. If no word matches the pattern, an empty list/array is returned. The order of words in the output does not matter.