[LeetCode] 438. Find All Anagrams in a String -슬라이딩 윈도우

아래의 문제는LeetCode의 문제 내용이며 코드는 직접 푼 내용입니다. 

 

---

[LeetCode] 438. Find All Anagrams in a String

 

 

요구사항

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

 

문자열2개(c,p)가 주어질때 p의 애너그램이 c의 어디위치에 나오는지 리턴

 

입출력예시

---

접근법

문자열을 애너그램단위만큼씩 짤라서 하나하나 애너그램인지까지 비교할 수도 있을 것이다.

하지만, 이번엔 슬라이딩 윈도우를 적용해보았다

 

결과

from collections import Counter
def findAnagrams(a,b):
    answer=[]
    m,n=len(a),len(b)
    if m<n: #예외사항 
        return answer
    bcounter = Counter(b)
    acounter = Counter(a[:n-1]) #n-1만큼 문자열자름(윈도우크기)
    
    print("애너그램문자열",bcounter) #Counter({'a': 1, 'b': 1})
    print("비교문자열",acounter) #Counter({'a': 1})

    end=0 #윈도우 맨뒤 인덱스
    for end in range(n-1,m):
        start=end-(n-1) #윈도우 맨앞 인덱스
        print(start,end)

        acounter[a[end]]+=1 #슬라이딩윈도우 맨뒤 추가
        print("맨뒤추가",acounter) #즉, a[end]라는 키값의 value를 +1
        if acounter==bcounter: #애너그램등장
            print("맨뒤 추가했더니 애너그램등장",acounter)
            answer.append(start) #정답 : 애너그램 등장한 위치

        acounter[a[start]]-=1 #슬라이딩윈도우 맨앞 빼기
        print("앞삭제",acounter) #즉, a[start]라는 키값의 value를 -1
        if acounter[a[start]] ==0: #실제로 value가 0이 된 key들은 삭제
            print("애너그램이랑 상관없어서 맨앞 삭제")
            del acounter[a[start]]
    return answer

a = "cbaebabacd"
b = "abc"

a1="abab"
b1="ab"
print(findAnagrams(a,b))

풀이과정

일단 내가 생각했을때 몇가지 핵심 아이디어는 3가지가 있다.

 

1. Counter 딕셔너리을 쓴다는 것이다. (from collections import Counter)

문자열을 key, 문자열의 등장횟수를 value를 가지고 있다. 

그리고 참고로, counter딕셔너리가 같다면 등장한 문자열과 그 문자열읟 등장횟수도 같으므로 애너그램으로 판단한다.

    answer=[]
    m,n=len(a),len(b)
    if m<n: #예외사항 
        return answer
    bcounter = Counter(b)
    acounter = Counter(a[:n-1]) #n-1만큼 문자열자름(윈도우크기)
    
    print("애너그램문자열",bcounter) #Counter({'a': 1, 'b': 1})
    print("비교문자열",acounter) #Counter({'a': 1})

 

2. 애너그램문자열의 크기-1 만큼 짜른다. 

예를 들어 a = "cbaebabacd" , b = "abc" 일때 b의 애너그램이 a의 어디위치에서 나타나는지 구해야한다.

이때, a를 비교문자열, b를 애너그램문자열 이라고 하자.

그럼 b의 애너그램이 어느위치에 나타는지 찾기 위해 a를 b크기와 똑같은 크기가 아니라 b크기-1만큼 자르는것이다.

 

결국, 슬라이딩 윈도우 크기가 n-1이 되고,

슬라이딩윈도우에 문자열을 하나 추가하고, 그!때! 애너그램이 되는지 검사를 할 수 있기 때문이다.

슬라이딩 윈도우크기가 n-1이라는 것은 end-start = n-1 이라고 이해했다. 

그래서 슬라이딩 윈도우를 계산하기 위해 end는 n-1부터 비교문자열 끝까지 반복되며 그때 start는 end- (n-1)이다. 

    end=0 #윈도우 맨뒤 인덱스
    for end in range(n-1,m):
        start=end-(n-1) #윈도우 맨앞 인덱스
        print(start,end)

 

3.슬라이딩윈도우 

보통 슬라이딩윈도우로 윈도우 안에 있는 값들을 계산하기 위해 subsum같은 별도의 list를 만들었는데,

여기에선 counter딕셔너리가 이에 해당한다. 슬라이딩 윈도우 자체가 비교문자열의 counter 딕셔너리가 된다.

 

슬라이딩 윈도우 맨 뒤를 추가할때는,

비교문자열[end]가 key값이 되어 그 슬라이딩 윈도우의 맨끝문자열이 한번더 나왔다고 value를 +1한다. 

그리고  애너그램이 등장했을때 정답을 저장한다.

        acounter[a[end]]+=1 #슬라이딩윈도우 맨뒤 추가
        print("맨뒤추가",acounter) #즉, a[end]라는 키값의 value를 +1
        if acounter==bcounter: #애너그램등장
            print("맨뒤 추가했더니 애너그램등장",acounter)
            answer.append(start) #정답 : 애너그램 등장한 위치

 

슬라이딩 윈도우 맨 앞을 삭제할때는,

비교문자열[start]가 key값이 되어 그 슬라이딩 윈도우의 맨앞문자열은 사라진다고 value를 -1한다. 

        acounter[a[start]]-=1 #슬라이딩윈도우 맨앞 빼기
        print("앞삭제",acounter) #즉, a[start]라는 키값의 value를 -1
        if acounter[a[start]] ==0: #실제로 value가 0이 된 key들은 삭제
            print("애너그램이랑 상관없어서 맨앞 삭제")
            del acounter[a[start]]

 

디버깅

주석과 디버깅과정을 통해 보면 슬라이딩 윈도우 과정을 이해하기 더 쉽다.

start가 0이고 end가 2일때 경우를 보면 

처음에 슬라이딩 윈도우 맨뒤에 end값을 추가해서 a:1 이 추가되었다. -> 애너그램 등장으로 정답처리

슬라이딩 윈도우 맨앞에 start값 삭제해해서 c:1이 c:0으로 변경되었다. value값이 -1되었다 -> value가 0인 key삭제

 

이렇게 반복적으로 슬라이딩 윈도우를 진행하면서 스캔하는 문자열은

슬라이딩윈도우로 맨처음 추가한 counter의 key만 보면 cba->bae->aeb->eba->bab->aba->bac->acd 이렇다.

 

배운점

• 애너그램을 구하기 위해 슬라이딩 윈도우를 쓸 경우, 윈도우의 크기는 n-1 (end-start = 윈도우크기)
• 애너그램을 구하기 위해 슬라이딩 윈도우를 쓸 경우, 윈도우는 counter 딕셔너리 그 자체
• 딕셔너리 값 삭제하기 위해서 del 딕셔너리[key]

유사문제 - 애너그램인지 확인

2021.07.12 - [Python] 문자열 애너그램(Anagrams) | Counter(), DefaultDict()

 

---

참고 

참고한 블로그 링크

http://ouwang.me/2018/12/22/Python-LeetCode-438-Find-All-Anagrams-in-a-String/

Python | LeetCode 438 | Find All Anagrams in a String