Find All Anagrams in a String [leetcode]

문제

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Find All Anagrams in a String - LeetCode

문제

 

문제 풀이 설명

긴 문자열 (이하 s) 에서 짧은 문자열(이하 p)의 anagram(알파벳 순서를 바꾼 문자열) 을 찾는 문제이다.

해당 문자열이 s에서 발견될 경우, 발견된 위치를 전부 리턴하면 되는 문제이다.

 

anagram은 문자의 순서를 바꿔 단어를 만들기 때문에 특정 알파벳의 존재유무와 개수 만을 비교하면 된다.

적절한 저장형태로 key : value 형태인 dictionary를 선택한다.

 

가령 “abc” 와 “bca”는 anagram이고, dictionary 형태로 바꾸면 (알파벳과 해당 알파벳의 등장횟수)

{ “a” : 1 , “b” : 1 , “c” : 1 } 로 동일하다는 걸 알 수 있다.

 

우선 문자열 → dictionary 로 바꿔주는 함수를 생성한다.

def buildDict(self, s):
    temp_dict = dict()
    for al in s:
        if al in temp_dict:
            temp_dict[al] += 1
        else:
            temp_dict[al] = 1
    return temp_dict

 

두번째로는 s의 부분 문자열의 dictionary , p의 dictionary를 비교하는 함수를 생성한다.

두 dictionary 가 같은지 비교할때는 체크 할 것이 두가지 있다.

1. key의 개수와, 동일한 key로 이뤄져 있는지
2. 동일한 key에 대해 value 값이 같은지

해당 체크사항을 토대로 함수를 생성한다.

def dictCompare(self, dict1, dict2):
    dict1_keySet = set(dict1.keys()) #key 값만으로 set을 생성
    dict2_keySet = set(dict2.keys()) 
    
		# 동일한 key를 가지고 있는지 검사
    if len(dict1_keySet - dict2_keySet) == 0 and len(dict2_keySet - dict1_keySet) == 0:
        for key in dict1.keys(): # 같은 key에 대한 value 값 역시 같은지 확인
            if dict1[key] != dict2[key]: # 같지 않다면 False 리턴
                return False 
        return True
    else: # key 값이 동일하지 않다면 두 dictionary 는 같지 않다.
        return False

 

이 두 함수를 이용해 s의 부분문자열과 p 간의 비교를 수행한다.

def findAnagrams(self, s: str, p: str) -> List[int]:
    answer = []
    p_len = len(p)
    dict1 = self.buildDict(p) #p -> dictionary
    
    dict2 = {}
    for i in range(0, len(s) - p_len + 1):
        part_s = s[i:i+p_len] #p 의 길이만큼 부분문자열 생성
        if i == 0: # dictionary 생성이 처음이라면 
            dict2 = self.buildDict(part_s) # part_s -> dictionary
        else: # dictionary 가 존재한다면
            dict2[s[i-1]] -= 1 # 한자리 이동한 만큼 해당 문자를 dictionary 에서 제거
            if dict2[s[i-1]] == 0: # dictionary value = 0 이라면 key 역시 제거
                del dict2[s[i-1]]
                
            if part_s[-1] in dict2: # 한자리 이동한 만큼 해당 문자를 dictionary 에 추가
                dict2[part_s[-1]] += 1
            else:
                dict2[part_s[-1]] = 1
        if self.dictCompare(dict1, dict2): # 두개의 dict를 비교
            answer.append(i) # 두개의 dict가 같다면 answer 에 index를 저장
    
    return answer

 

전체 코드

class Solution:
    def dictCompare(self, dict1, dict2):
        dict1_keySet = set(dict1.keys())
        dict2_keySet = set(dict2.keys())
        
        if len(dict1_keySet - dict2_keySet) == 0 and len(dict2_keySet - dict1_keySet) == 0:
            for key in dict1.keys():
                if dict1[key] != dict2[key]:
                    return False
            return True
        else:
            return False
        
    def buildDict(self, s):
        temp_dict = dict()
        for al in s:
            if al in temp_dict:
                temp_dict[al] += 1
            else:
                temp_dict[al] = 1
        return temp_dict
    
    def findAnagrams(self, s: str, p: str) -> List[int]:
        answer = []
        p_len = len(p)
        dict1 = self.buildDict(p)
        
        dict2 = {}
        for i in range(0, len(s) - p_len + 1):
            part_s = s[i:i+p_len]
            if i == 0:
                dict2 = self.buildDict(part_s)
            else:
                dict2[s[i-1]] -= 1
                if dict2[s[i-1]] == 0:
                    del dict2[s[i-1]]
                    
                if part_s[-1] in dict2:
                    dict2[part_s[-1]] += 1
                else:
                    dict2[part_s[-1]] = 1
            if self.dictCompare(dict1, dict2):
                answer.append(i)
        
        return answer

 

결과는 다음과 같다.