2018年9月16日
#890. Find and Replace Pattern
问题描述：
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.
样例:
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.问题分析：
本题难度为Medium！已给出的函数定义为：
class Solution:def findAndReplacePattern(self, words, pattern):""":type words: List[str]:type pattern: str:rtype: List[str]"""其中words是字符串数组，pattern为字符串；返回值是一个字符串数组。
算法如下：
遍历words的每一个字符串元素与pattern进行匹配，若符合，则存储该字符串到数组中；
进行匹配判断时，创建两个字典m1、m2，分别存储words字符串元素的字符到pattern字符串的字符的映射和pattern字符串的字符到words字符串元素的字符的映射，若关键字key不存在，则添加映射；
判断(m1[w],m2[p])==(p,w)是否成立，即映射是否为一一映射，若不是，则不匹配，若全部成立，则匹配；
将匹配的字符串添加到数组中；
代码实现如下：
class Solution:def findAndReplacePattern(self, words, pattern):""":type words: List[str]:type pattern: str:rtype: List[str]"""res=[]for word in words:m1, m2 = {}, {}isMatch=Truefor i in range(len(pattern)):w = word[i]p = pattern[i]if w not in m1: m1[w] = pif p not in m2: m2[p] = wif (m1[w], m2[p]) != (p, w):isMatch=Falsebreakif isMatch:res.append(word)return res由于python为我们提供了两个便捷强大的函数zip()和filter()，因此代码可以进一步简化，以下代码是官方提供的标准代码：
class Solution:def findAndReplacePattern(self, words, pattern):""":type words: List[str]:type pattern: str:rtype: List[str]"""def match(word):m1, m2 = {}, {}for w, p in list(zip(word, pattern)):if w not in m1:m1[w] = pif p not in m2:m2[p] = wif (m1[w], m2[p]) != (p, w):return Falsereturn Truereturn list(filter(match, words))zip() 函数用法
filter() 函数用法