题目描述

你有列表words和一个字符串pattern，你想知道words列表中哪些单词能够匹配上pattern.

一个单词能匹配上pattern的要求是能找到一个单词的映射p，要求对pattern中的每个字母pattern[i]，都有p(pattern[i])=word[i]，要求字母映射是一一对应的。

返回能匹配到pattern的单词列表，返回的单词列表顺序不作要求。

样例

输入: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出: ["mee","aqq"]
说明: "mee"能与pattern匹配因为存在这样的映射(a->m, b->e)，
而"ccc"不能与pattern匹配因为(a->c, b->c)不是一个合法映射，
a和b不能映射到同一个字母。

算法1

(字典) $O(n)$

用字典p2w记录pattern字母对word字母的对应关系，w2p是word字母对pattern字母的对应关系，需要保证同一个pattern字母不能对应两个不同的word字母，不同的pattern字母不能对应到同一个word字母。
对于pattern中的每个字母pattern[i]，查看是否已经有了映射关系，如果已经映射到了一个word字母，比较该字母是否与word[i]相同，若不同则说明pattern[i]需要对应到两个不同的word字母，不满足要求。若还未映射到word字母，则说明需要增加一个pattern->word的映射关系，再检查word[i]是否已经被别的pattern字母对应，若已经有pattern字母对应到word[i]且不等于pattern[i]，则说明不满足要求。

时间复杂度分析：O(n)，n是words列表中单词的总长度。

Python 代码

class Solution:
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        ans = []
        for word in words:
            flag = True
            w2p = {}//word字母到pattern字母的对应关系
            p2w = {}//pattern字母到word字母的对应关系
            for i in range(0, len(pattern)):
                p = pattern[i]
                if p in p2w:
                    if p2w[p] != word[i]:
                        flag = False
                        break
                else:
                    if word[i] in w2p:
                        flag = False
                        break
                    p2w[p] = word[i]
                    w2p[word[i]] = p
            if flag:
                ans.append(word)
        return ans