## Algorithm

Problem Name: 890. Find and Replace Pattern

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 `x` in 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.

Example 1:

```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:

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

Constraints:

• `1 <= pattern.length <= 20`
• `1 <= words.length <= 50`
• `words[i].length == pattern.length`
• `pattern` and `words[i]` are lowercase English letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string>res;
for (auto& s: words) {
if (isValid(s, pattern)) {
res.push_back(s);
}
}
return res;
}

bool isValid(string& a, string& b) {
unordered_map < char, char>m, t;
int n = a.size(), l = b.size();
if (n != l) {
return false;
}

for (int i = 0; i  <  n; ++i) {
if (m.count(a[i]) || t.count(b[i])) {
if (m[a[i]] == b[i] && t[b[i]] == a[i]) {
continue;
} else {
return false;
}
}
m[a[i]] = b[i];
t[b[i]] = a[i];
}
return true;
}
};

class Solution {
public:
vector < string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string>res;
for (auto& s: words) {
if (normalize(s) == normalize(pattern)) {
res.push_back(s);
}
}
return res;
}

string normalize(string& s) {
unordered_map < char, char>m;
string res;
char c = 'a';
for (auto& x: s) {
if (!m.count(x)) {
m[x] = c++;
}
}
for (auto& x: s) {
res.push_back(m[x]);
}
return res;
}
};
``````
Copy The Code &

Input

cmd
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

Output

cmd
["mee","aqq"]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List findAndReplacePattern(String[] words, String pattern) {
String patternString = getPattern(pattern);
return Arrays.stream(words).filter(e -> getPattern(e).equals(patternString))
.collect(Collectors.toList());
}

private String getPattern(String s) {
StringBuilder sb = new StringBuilder();
Map < Character, Integer> map = new HashMap<>();
int count = 1;
for (char c : s.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, count++);
}
sb.append(map.get(c));
}
return sb.toString();
}
}
``````
Copy The Code &

Input

cmd
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

Output

cmd
["mee","aqq"]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findAndReplacePattern = (words, pattern) => {
return words.reduce((acc, item, index) => {
if (compose(words[index], pattern)) acc.push(words[index]);
return acc;
}, []);

function compose(element, pattern) {
const s = new Set();
const m = new Map();
for (let i = 0; i  <  element.length; i++) {
const e = element[i];
const p = pattern[i];
if (m.get(p) === undefined) {
m.set(p, e);
} else if (m.get(p) !== e) {
return false;
}
}
return m.size === s.size;
}
};
``````
Copy The Code &

Input

cmd
words = ["a","b","c"], pattern = "a"

Output

cmd
["a","b","c"]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findAndReplacePattern(self, words, pattern):
"""
:type words: List[str]
:type pattern: str
:rtype: List[str]
"""
res = []
for w in words:
mp12, mp21, match = {}, {}, True
for c1, c2 in zip(w, pattern):
if (c1 in mp12 and mp12[c1] != c2) or (c2 in mp21 and mp21[c2] != c1):
match = False
break
mp12[c1], mp21[c2] = c2, c1
if match: res.append(w)
return res
``````
Copy The Code &

Input

cmd
words = ["a","b","c"], pattern = "a"

Output

cmd
["a","b","c"]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0890_FindAndReplacePattern
{
public IList < string> FindAndReplacePattern(string[] words, string pattern)
{
var result = new List();
foreach (var word in words)
if (Match(word, pattern))

return result;
}

private bool Match(string word, string pattern)
{
var map1 = new Dictionary < char, char>();
var map2 = new Dictionary();
for (int i = 0; i  <  pattern.Length; i++)
{
if (!map1.ContainsKey(pattern[i]))
map1[pattern[i]] = word[i];
if (!map2.ContainsKey(word[i]))
map2[word[i]] = pattern[i];

if (map1[pattern[i]] != word[i] || map2[word[i]] != pattern[i])
return false;
}

return true;
}
}
}
``````
Copy The Code &

Input

cmd
words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

Output

cmd
["mee","aqq"]