# [LeetCode] 890. Find and Replace Pattern 查找和替换模式

2021年09月15日 阅读数：4

You have a list of `words` and a `pattern`, and you want to know which words in `words` matches the pattern.html

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.java

(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.)python

Return a list of the words in `words` that match the given pattern. 数组

You may return the answer in any order.函数

Example 1:post

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

Note:url

• `1 <= words.length <= 50`
• `1 <= pattern.length = words[i].length <= 20`

Java:htm

```public List<String> findAndReplacePattern(String[] words, String pattern) {
int[] p = F(pattern);
List<String> res = new ArrayList<String>();
for (String w : words)
if (Arrays.equals(F(w), p)) res.add(w);
return res;
}

public int[] F(String w) {
HashMap<Character, Integer> m = new HashMap<>();
int n = w.length();
int[] res = new int[n];
for (int i = 0; i < n; i++) {
m.putIfAbsent(w.charAt(i), m.size());
res[i] = m.get(w.charAt(i));
}
return res;
}```

Python:

```# Time:  O(n * l)
# Space: O(1)
import itertools

class Solution(object):
def findAndReplacePattern(self, words, pattern):
"""
:type words: List[str]
:type pattern: str
:rtype: List[str]
"""
def match(word):
lookup = {}
for x, y in itertools.izip(pattern, word):
if lookup.setdefault(x, y) != y:
return False
return len(set(lookup.values())) == len(lookup.values())

return filter(match, words)
```

Python:

```def findAndReplacePattern(self, words, p):
def F(w):
m = {}
for c in w: m[c] = m.get(c, len(m))
return "".join(chr(m[c] + 97) for c in w)
return [w for w in words if F(w) == F(p)]　```

Python: Similar to isomorphic string, check the length of the sets and the length of the set when the characters are zipped together.

```b = pattern
def is_iso(a):
return len(a) == len(b) and len(set(a)) == len(set(b)) == len(set(zip(a, b)))
return filter(is_iso, words)　```

C++:

```vector<string> findAndReplacePattern(vector<string> words, string p) {
vector<string> res;
for (string w : words) if (F(w) == F(p)) res.push_back(w);
return res;
}

string F(string w) {
unordered_map<char, int> m;
for (char c : w) if (!m.count(c)) m[c] = m.size();
for (int i = 0; i < w.length(); ++i) w[i] = 'a' + m[w[i]];
return w;
}
```

C++:

```// Time:  O(n * l)
// Space: O(1)
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> result;
for (const auto& word: words) {
if (match(word, pattern)) {
result.emplace_back(word);
}
}
return result;
}

private:
bool match(const string& word, const string& pattern) {
unordered_map<char, char> lookup;
unordered_set<char> char_set;
for (int i = 0; i < word.length(); ++i) {
const auto& c = word[i], &p = pattern[i];
if (!lookup.count(c)) {
if (char_set.count(p)) {
return false;
}
char_set.emplace(p);
lookup[c] = p;
}
if (lookup[c] != p) {
return false;
}
}
return true;
}
};
```

[LeetCode] 205. Isomorphic Strings 同构字符串