LeetCode 76. [Python] Minimum Window Substring
原题链接
困难
作者:
徐辰潇
,
2021-02-01 02:25:12
,
所有人可见
,
阅读 444
class Solution:
def minWindow(self, s: str, t: str) -> str:
#TS: O(len(s))
#SC: O(len(t))
if len(t) > len(s):
return ""
Dict = {} #key: char in t; value: number of appearances in t originally
#When the sliding window process starts, Dict[c] represents the number of apperances of c in t than in s.
#If Dict[c] < 0, it means s contains c more than t
for c in t:
if c not in Dict:
Dict[c] = 1
else:
Dict[c] += 1
N = len(Dict)#Total number of unique char in t
count = 0 #total number of unique char in t that also appears in s
#If count == N, then it consitutes a satisfied minimum window
left = 0
right = 0
res = ''
MinLen = sys.maxsize
while right < len(s):
#enlarge the window to the right
#it meets char in t, taking record in Dict and count
if s[right] in Dict:
Dict[s[right]] -= 1
if Dict[s[right]] == 0:
count += 1
#Actually this while contains to meanings
#1.if (count == N)
#2. while(left <= right)
while(left <= right and count == N):
Len = right + 1 - left
if Len < MinLen:
res = s[left:right+1]
MinLen = Len
if s[left] in Dict:
Dict[s[left]] += 1
if Dict[s[left]] == 1:
count -= 1
left += 1
right += 1
return res