[LeetCode] 890. Find and Replace Pattern

 

890. Find and Replace Pattern

Medium

2584138Add to ListShare

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"]

 

Constraints:

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

 

---

문제 풀이

문제 접근

1. 패턴과 단어들이 주어진다.
2. 패턴과 단어의 길이는 같다.
3. 단어들의 길이는 최대 50개이다.
4. Time Complexity: N^2도 가능할 것 같다.

해설

1. 패턴의 순서와 알파벳을 변경하여 단어와 같으면 답 리스트에 추가해야한다. 패턴의 알파벳은 어느 소문자 알파벳으로도 변경이 가능하지만, 하나의 알파벳은 다른 하나의 알파벳으로만 변경가능하다. 'abc' -> 'def', 'a' -> 'd' 
2. 패턴과 단어를 모두 확인해볼 수 밖에 없다. 
3. 패턴을 알파벳 단위로 확인하면 더 복잡해진다.
4. 딕셔너리를 사용하여 각 알파벳의 인덱스를 벨류로 저장한다. 
5. 0부터 시작하는 인덱스로 저장하면 각 단어들의 패턴을 확인할 수 있다. 
6. 패턴의 인덱스를 딕셔너리에 저장하고, 단어를 확인할때 새로운 딕셔너리로 단어의 인덱스를 딕셔너리로 저장하여 비교한다.

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        if len(pattern) == 1:
            return words
        ans = []
        patternmap = dict()
        ptemp = ''
        index0 = 0
        for w in pattern:
            if w not in patternmap:
                patternmap[w] = index0
                ptemp += str(index0)
                index0 += 1
            else:
                ptemp += str(patternmap[w])
        # print('p', ptemp)
        for word in words:
            index = 0
            wordmap = dict()
            temp = ''
            for w in word:
                if w not in wordmap:
                    wordmap[w] = index
                    temp += str(index)
                    index += 1
                else:
                    temp += str(wordmap[w])
            if temp == ptemp:
                ans.append(word)
            # print(temp)
        return ans