[Leetcode] 438. Find All Anagrams in a String

floatFirstTOC: right

🖥️ 시작하며

1. 초반 i 가 p_length 보다 작을 때까지:

if s_count == p_count:
    res.append(i - p_length + 1)

위 if문은 지나치고 아래 구문에 걸린다. s_count 카운터와 p_count 카운터가 같다면 res 에 시작 인덱스를 추가한다.
• 여기서 "cba" 와 "abc" 가 같기 때문에 0이 res에 추가됨
 

2. 이후 초반 i 가 p_length 보다 크면 :

if s_count[s[i - p_length]] == 1: # 이전 루프의 맨 왼쪽 문자 삭제
    del s_count[s[i - p_length]]
else:
    s_count[s[i - p_length]] -= 1

슬라이스 윈도우의 크기가 커지는 것을 방지하기 위해 s_count[s[i - p_length]] == 1 조건으로 이전 루프에서의 맨 왼쪽 문자를 제거하도록 한다.
또한 중복 문자열이 들어가 있을 가능성이 있으므로 만일 if문에 걸러지지 않았다면 그냥 -1 처리를 해 준다.
 
• 여기서 i = 3 이고 p_length = 3 이므로 s[i - p_length] 는 "c"
• s_count의 "c"에 대한 빈도를 감소시킨다.

⚙️ Python

from collections import Counter
from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        p_count = Counter(p)
        s_count = Counter()
        p_length = len(p)

        for i in range(len(s)):
            s_count[s[i]] += 1

            if i >= p_length:
                if s_count[s[i - p_length]] == 1:
                    del s_count[s[i - p_length]]
                else:
                    s_count[s[i - p_length]] -= 1

            if s_count == p_count:
                res.append(i - p_length + 1)

        return res


if __name__ == "__main__":
    sol = Solution()
    print(sol.findAnagrams("cbaebabacd", "abc"))  # [0, 6]

📌 소감