[알고리즘] Leetcode #76 부분 문자열이 포함된 최소 윈도우 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

Given two strings s and t of lengths m and n respectively, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

 

입출력 예

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC"

Example 2:

Input: s = "a", t = "a" Output: "a"

 

Constraints

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of English letters.

* Follow up: Could you find an algorithm that runs in O(m + n) time?

 

Code

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]

 

이 문제는 O(n) 안에 풀어야 하는 문제로, 투포인터와 슬라이딩 윈도우를 사용했다. 우선 첫 번째 for문을 돌면서, s 문자열 안에 t 문자열 중 하나가 매칭될 때마다 missing은 하나씩 줄어들도록 하고, need Counter는 매칭되는 문자는 0, 매칭되지 않는 문자는 음수 값을 갖도록 만든다. 이후, missing이 0이 되는 순간 (t의 모든 문자가 s에서 모두 발견), 필요 없는 문자 (음수) 에서 벗어날 때까지 left를 1개씩 늘리면서 윈도우의 크기를 줄인다. (최소 윈도우를 구해야 하기 때문)  이후 s 문자열에서 start ~ end까지의 문자를 슬라이싱해 return한다. 

 

---

 

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)