---
# System prepended metadata

title: 890. Find and Replace Pattern
tags: [Leetcode, medium, python, hash]

---

###### 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:
``` 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']
```