[알고리즘] 부분 문자열이 포함된 최소 윈도우

부분 문자열이 포함된 최소 윈도우

책 풀이

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        missing = len(t)
        left = start = end = 0
        # 오른쪽 포인터 이동
        for right, char in enumerate(s, 1): # 1부터 시작하겠다는 의미다.
            missing -= need[char] > 0 # 만약 현재 문자가 필요한 문자 need[char]에 포함되어 있다면 
            # 필요한 문자의 전체 개수인 missing을 1 감소한다. 
            need[char] -= 1

            # 필요 문자가 0이면 왼쪽 포인터 이동 판단
            if missing == 0:
                while left < right and need[s[left]] < 0:
                    need[s[left]] += 1
                    left += 1

                if not end or right - left <= end - start:
                    start, end = left, right

                need[s[left]] += 1
                missing += 1
                left += 1
        return s[start:end]

sol = Solution()
print(sol.minWindow("ADOBECODEBANC", "ABC"))

코드만 봐서는 직관적으로 이해가 가지 않는다. A에서 시작해서 필요한 ABC가 다 생기면 A를 제외하고 B부터 시작해서 다음 A가 있는 곳까지 찾고.. 반복이다.

missing이 0이되면, 즉 필요하누 문자의 개수가 0이 된다면 이제 왼쪽 포인터를 더 줄일수 있는ㄴ지 살핀다. 기준은 음수인 경우다. 즉 왼쪽 포인터가 불필요한 문자를 가리키고 있다면 분명 음수일 것이고, 0을 가리키는 우치까지 왼쪽 포인터를 이동한다.