题解 | #最小覆盖子串#

class Solution:
    def check(self,hashset):
        for i in hashset:
            if hashset[i]<0:
                return False
        return True
    def minWindow(self , S: str, T: str) -> str:
        len_S=len(S)
        #记录所有的应该匹配的字符个数，全都置为相应个数的-x个
        hashset={i:0 for i in T}
        for i in T:
            hashset[i]-=1
        left=right=0
        results=[]

        while right<len_S:
            #如果没有全部找到，则扩张右边界直到全部找到
            if S[right] in T:
                hashset[S[right]]+=1
            while self.check(hashset):#如果已经全部找到了，则缩短左边界
                if S[left] in T:#如果当前这个字符在T里
                    if hashset[S[left]]==0:#如果减去这个就正好不满足情况了,说明当前这个是最短的,记录一下
                        results.append([left,right])
                    hashset[S[left]]-=1
                left+=1
            right += 1

        #此时遍历results,寻找最小的那个子串
        final_right,final_left=0,0
        minlen=999999
        if len(results)==0:
            return ""
        for result in results:
            left,right=result
            if right-left<minlen:
                minlen=right-left
                final_left,final_right=left,right
        return S[final_left:final_right+1]