890. Find and Replace Pattern
Medium
2584138Add to ListShareGiven 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.
문제 풀이
문제 접근
- 패턴과 단어들이 주어진다.
- 패턴과 단어의 길이는 같다.
- 단어들의 길이는 최대 50개이다.
- Time Complexity: N^2도 가능할 것 같다.
해설
- 패턴의 순서와 알파벳을 변경하여 단어와 같으면 답 리스트에 추가해야한다. 패턴의 알파벳은 어느 소문자 알파벳으로도 변경이 가능하지만, 하나의 알파벳은 다른 하나의 알파벳으로만 변경가능하다. 'abc' -> 'def', 'a' -> 'd'
- 패턴과 단어를 모두 확인해볼 수 밖에 없다.
- 패턴을 알파벳 단위로 확인하면 더 복잡해진다.
- 딕셔너리를 사용하여 각 알파벳의 인덱스를 벨류로 저장한다.
- 0부터 시작하는 인덱스로 저장하면 각 단어들의 패턴을 확인할 수 있다.
- 패턴의 인덱스를 딕셔너리에 저장하고, 단어를 확인할때 새로운 딕셔너리로 단어의 인덱스를 딕셔너리로 저장하여 비교한다.
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
'컴퓨터공학 > LeetCode 1000' 카테고리의 다른 글
[LeetCode] 916. Word Subsets (0) | 2022.07.30 |
---|---|
[LeetCode] 251. Flatten 2D Vector (0) | 2022.07.29 |
물건 사고 파는 문제 파이썬 order, sell, return (0) | 2022.03.07 |
a+b=c 숫자식에서 각 숫자의 한자리 수 치환을 통해 식을 맞게 만드는 방법 (0) | 2022.03.07 |
[LeedCode] 929. Unique Email Addresses 파이썬 (Easy) (0) | 2021.12.21 |