[Hard-Biptr] 76. Minimum Window
2019-10-16 本文已影响0人
Mree111
Description
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Solution
思路,使用双指针left记录start, right 记录cover 的end
(思路好像,代码异常难写)
class Solution:
def build_dict(self,t):
res ={}
for c in list(t):
if c in res:
res[c] +=1
else:
res[c] = 1
return res
def minWindow(self, s: str, t: str) -> str:
if len(s)< len(t):
return ""
c_dict = self.build_dict(t) # char needed for template
start = 0
char_cnt = 0
min_len = 1e6
idx = 0
s = list(s)
for end in range(len(s)):
if s[end] in c_dict:
c_dict[s[end]]-=1
if c_dict[s[end]]==0: ##注意条件
char_cnt +=1
else:
continue
# check if substr covered the template
while char_cnt == len(c_dict): #注意条件
if min_len > end-start +1:
min_len = end-start +1
idx = start
# move forward for start point
ch = s[start]
start+=1 #注意更新
if ch not in c_dict:
continue
c_dict[ch]+=1
if c_dict[ch] >0:
char_cnt -= 1
if min_len == 1e6:
return ""
return "".join(s[idx:idx+min_len])