[파이썬 알고리즘 인터뷰][슬라이딩윈도우] 부분 문자열이 포함된 최소 윈도우

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

t의 모든 문자, 개수가 포함된 s의 최소 윈도우 출력

 

책에서 구현된 코드

import collections


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):
            missing -= need[char] > 0
            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]

 

기억해야할 기법

• Counter가 defaultdict인듯 하다
  • 위 코드 need[char]에서 char가 t의 Counter에 포함되지않을 수 있는데 사용

 

내가 구현한 코드

class Solution:
    def minWindow(self, s: str, pattern: str) -> str:
        dic_pattern = Counter(pattern)
        dic_pattern["total"] = len(set(pattern))
        q = deque()
        l, r = 0, -1

        for i, c in enumerate(s):
            if c in dic_pattern:
                q.append((i, c))

                dic_pattern[c] -= 1
                if dic_pattern[c] == 0:
                    dic_pattern["total"] -= 1

                if dic_pattern["total"] == 0:
                    while dic_pattern[q[0][1]] < 0:
                        idx, char = q.popleft()
                        dic_pattern[char] += 1

                    if r-l < 0 or q[-1][0]-q[0][0] < r-l:
                        l, r = q[0][0], q[-1][0]

        return s[l:r+1]

• 풀긴 풀었는데 지저분한 느낌이다
• deque를 사용해서 그런지 책의 알고리즘이랑 시간차이가 크다