[LeetCode][Python] 567. Permutation in String

- 문제 링크: https://leetcode.com/problems/permutation-in-string/

- 난이도: Medium

 

문자열 s1, s2가 주어질 때, s1을 애너그램한 문자열이 s2에 포함되어 있냐 판단하는 문제다

s1만큼의 window를 만들고, 알파벳 별 숫자를 세서(=histogram) 업데이트한다. s1과 s2 윈도우의 histogram이 일치하면 True. dict는 순서 상관 없이 entry가 같으면 같다.

 

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        h1 = defaultdict(int)
        for c in s1:
            h1[c] += 1

        h2 = defaultdict(int)
        for i in range(len(s1)):
            h2[s2[i]] += 1
        
        if h1 == h2:
            return True

        for r in range(len(s1), len(s2), 1):
            l = r - len(s1)
            h2[s2[r]] += 1
            h2[s2[l]] -= 1

            if h2[s2[l]] == 0:
                h2.pop(s2[l])

            if h1 == h2:
                return True

        return False