단어 목록과 패턴이 있고 단어에서 패턴과 일치하는 단어를 찾아야 한다고 가정합니다. 여기서 단어는 문자 p의 순열이 있는 경우 패턴과 일치하므로 패턴의 모든 문자 x를 p(x)로 바꾼 후 대상 단어를 얻습니다. 주어진 패턴과 일치하는 단어의 목록을 찾아야 합니다.
예를 들어 입력이 ["abc","deq","mee","aqq","dkd","ccc"]이고 패턴이 "abb"인 경우 출력은 ["mee" , "aqq"], 여기서 mee와 aqq는 패턴 "abb"의 스타일과 일치합니다. 그러나 "ccc"는 순열이 아니기 때문에 패턴이 아닙니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 하나의 convert() 메서드를 정의합니다. 이것은 단어를 입력으로 사용하며 다음과 같이 작동합니다. -
- 카운터 :=1, s :=빈 문자열
- s :=s + 카운터와 동일한 문자열
- i 범위 1에서 단어 길이 – 1
- j :=나는 – 1
- j>=0
- 동안
- 단어[j]가 단어[i]이면 중단
- j를 1 감소
- j> -1이면 s :=s + s[j], 그렇지 않으면 카운터를 1만큼 증가시키고 s :=s + 카운터 값을 문자열로 증가
- 반환
- 실제 방법은 다음과 같습니다.
- 하나의 배열 word_num을 만들고 이것은 비어 있고 다른 빈 배열 res 를 만듭니다.
- 단어의 각 요소 i에 대해 −
- convert(i)를 word_num에 삽입
- 패턴 :=변환(패턴)
- 0에서 단어 길이까지 범위에 있는 i의 경우 – 1
- words_num[i] =패턴이면 단어[i]를 res에 삽입
- 반환 결과
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class Solution(object): def findAndReplacePattern(self, words, pattern): words_num = [] result = [] for i in words: words_num.append(self.convert(i)) pattern = self.convert(pattern) for i in range(len(words)): if words_num[i] == pattern: result.append(words[i]) return result def convert(self,word): counter = 1 s = "" s+=str(counter) for i in range(1,len(word)): j= i -1 while j>=0: if word[j] == word[i]: break j-=1 if j >-1: s+=s[j] else: counter+=1 s+=str(counter) return s ob = Solution() print(ob.findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"],"abb"))
입력
["abc","deq","mee","aqq","dkd","ccc"] "abb"
출력
['mee', 'aqq']