[LeetCode] 890 | Find and Replace Pattern | Python

---

문제 링크: 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.

---

조건

• 1 <= pattern.length <= 20
• 1 <= words.length <= 50
• words[i].length == pattern.length
• pattern and words[i] are lowercase English letters.

---

내 풀이

word와 pattern안의 알파벳은 각각 하나씩 매칭되어야 한다.

아래 예시를 보자.

words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"

word가 'abc'일 때는 (a, a), (b, b), (c, b)로 매칭되는데, pattern의 b가 word의 b와 c, 두개로 매칭된다. 따라서 이 경우는 pattern에 해당하지 않는다.

word가 'mee'일 때는 (m, a), (b, e), (b, e)로 매칭되기 때문에 이 경우에는 pattern에 해당된다.

---

코드

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = []
        for word in words:
            w2p, p2w = {}, {}
            check = 1
            
            for w, p in zip(word, pattern):
                if w in w2p.keys():
                    if w2p[w] != p:
                        check = 0
                        break
                
                if p in p2w.keys():
                    if p2w[p] != w:
                        check = 0
                        break
                
                w2p[w], p2w[p] = p, w
            
            if check:
                ans.append(word)
        
        return ans