题解 | #最小覆盖子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:

    def check(self,hash):  # 检查是否都出现过
        for i in hash:
            if hash[i] <= 0:
                return False
        return True

    def minWindow(self , S: str, T: str) -> str:
        hash = {}
        for char in T:
            if char in hash:
                hash[char] -= 1
            else:
                hash[char] = 0
        res_len = 999
        res = ''

        i = 0 #右
        j = 0 #左
        while i < len(S):
            while not self.check(hash): # 检查是否满足都出现过
                if S[i] in hash:
                    hash[S[i]] += 1
                i += 1
                if i == len(S) and not self.check(hash): # 到最后的还不满足，可以直接返回
                    return res
            while self.check(hash): # 移动左指针。如果不满足就停
                if S[j] in hash:
                    hash[S[j]] -= 1
                j += 1
            len_tmp = i-(j-1) # j要-1才满足
            if len_tmp < res_len:
                res_len = len_tmp
                res = S[j-1:i]
        return res