LeetCode 풀기 - 567. Permutation in String

567. Permutation in String

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

문제)

솔루션1)

스트링 매칭 문제입니다. 

슬라이딩 윈도우 방식을 통해서 문제를 해결합니다.

s1의 각 문자의 수를 세어서 윈도우 사이즈 만큼  s2에서 동일한 count 패턴이 나오는지 체크합니다.

# Sliding Window
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:        
        # 문자 -> 숫자 변환
        l1 = list(map(lambda x: ord(x) - ord('a'), s1))
        l2 = list(map(lambda x: ord(x) - ord('a'), s2))

        # s1 문자 카운트
        target = [0] * 26
        for x in l1:
            target[x] += 1

        # 초기 윈도우
        window = [0] * 26
        
        for i, x in enumerate(l2):
            # 윈도우 업데이트
            window[x] += 1
                    
            if i >= len(l1):
                # 윈도우 사이즈 범위를 넘어가는 이전 count 감소
                window[l2[i - len(l1)]] -= 1
                
            if target == window:
                return True
            
        return False

솔루션2)

솔루션1 방식이 슬라이딩 윈도우를 list 형태를 유지해서 해결했다면 여기서는 해쉬를 이용합니다.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:        
        target = collections.Counter(s1)
        window = collections.Counter(s2[:len(s1)])

        start = 0
        end = len(s1)

        while end < len(s2):
            if target == window:
                return True

            # decrease
            window[s2[start]] -= 1

            # Remove zero item
            if window[s2[start]] == 0:
                del window[s2[start]]

            # increase
            window[s2[end]] = window.get(s2[end], 0) + 1

            # move
            start += 1
            end += 1

        return target == window