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

@TOC

## # 题目描述

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

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

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

You may return the answer in any order.

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.

Note:

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

## # 解题方法

### # 字典+set

class Solution(object):
def findAndReplacePattern(self, words, pattern):
"""
:type words: List[str]
:type pattern: str
:rtype: List[str]
"""
ans = []
set_p = set(pattern)
for word in words:
if len(set(word)) != len(set_p):
continue
fx = dict()
equal = True
for i, w in enumerate(word):
if w in fx:
if fx[w] != pattern[i]:
equal = False
break
fx[w] = pattern[i]
if equal:
ans.append(word)
return ans

### # 单字典

Python代码如下：

class Solution(object):
def findAndReplacePattern(self, words, pattern):
"""
:type words: List[str]
:type pattern: str
:rtype: List[str]
"""
res = []
for word in words:
if len(word) != len(pattern): continue
d = dict()
isMatch = True
for i, c in enumerate(pattern):
if c in d:
if d[c] != word[i]:
isMatch = False
break
d[c] = word[i]
d = dict()
for i, c in enumerate(word):
if c in d:
if d[c] != pattern[i]:
isMatch = False
break
d[c] = pattern[i]
if isMatch:
res.append(word)
return res

C++代码如下：

class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> res;
for (string& word : words) {
bool isMatch = true;
map<char, char> d;
for (int i = 0; i < word.size(); i++) {
if (d.count(word[i])) {
if (d[word[i]] != pattern[i]) {
isMatch = false;
break;
}
}
d[word[i]] = pattern[i];
}
d.clear();
for (int i = 0; i < word.size(); i++) {
if (d.count(pattern[i])) {
if (d[pattern[i]] != word[i]) {
isMatch = false;
break;
}
}
d[pattern[i]] = word[i];
}
if (isMatch) res.push_back(word);
}
return res;
}
};

## # 日期

2018 年 8 月 24 日 —— Keep fighting! 2018 年 11 月 5 日 —— 打了羽毛球，有点累 2018 年 12 月 2 日 —— 又到了周日