###### tags: `Leetcode` `medium` `hash` `python`

# 890. Find and Replace Pattern

## [題目連結:] https://leetcode.com/problems/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"]

## 解題想法:
* 題目為找出words中所有滿足能映射到pattern的string
* 映射為string中每個char都與pattern中每個char關係一致
* ex: 'mee'->'abb'
* m->a
* e->b

* 使用hash_table
* init:
* dic: 存string的char分別對應到pattern哪個字符
* equal=True : 若string判斷完且equal仍為True，則表示可以加入最終res
* 因為題目words中每個string的長度都已經==len(pattern)，不用額外判斷
* 可以用個set，先判斷是否種類集合數量一樣
* ex:
* string: 'ccc' -> set(string)={c}
* pattern:'abb' -> set(pattern)={a,b}
* 因為len(set(string))!=len(set(pattern))
* 不可能成功一對一對應，所以可以不用再進一步判斷
* 每次判斷新的string，先將dic清空
* for pos,char in enumerate(string):
* if char in dic:
* 若dic[char]!=pattern[pos]
* 表示已經有人對應過了，代表多對一
* equal改為False then break
* dic[char]=pattern[pos]: 產生唯一對應
* 最終每個位置的char皆判斷完，且equal仍為True:
* res.append(string)

## Python:

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        dic={}
        res=[]
        setP=set(pattern)
        for string in words:
            if len(set(string))!=len(setP): #種類數量不同，不可能成功對應
                continue
            dic.clear() #清空
            equal=True
            for pos,char in enumerate(string):
                if char in dic:
                    if dic[char]!=pattern[pos]:
                        equal=False
                        break
                dic[char]=pattern[pos] #產生唯一對應
            if equal==True:
                res.append(string)
        return res

if __name__=='__main__':
    result=Solution()
    ans=result.findAndReplacePattern(words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb")
    print(ans) #['mee', 'aqq']