最小覆盖子串

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def exist_add(self, s: str, T: dict) -> dict:
        """
        判断当前字符是否在哈希表中
        """
        val = T.get(s)
        if val is not None:
            T[s] += 1
        return T

    def less_zero(self, obj) -> bool:
        """
        判断当前哈希表中是否有小于零的数
        """
        for ele in obj:
            if ele < 0:
                return True
        return False

    def minWindow(self , S: str, T: str) -> str:
        # 创建哈希表，用于检查T中数据是否存在
        tab_hash = {}
        for key in T:
            if tab_hash.get(key) is None:
                tab_hash[key] = -1
            else:
                tab_hash[key] -= 1
        # 窗口(通过双指针实现)遍历找寻最短的字串
        res = ''    # 用于保留最短的子串
        left = 0    # 左指针
        right = 0   # 右指针
        tab_hash = self.exist_add(S[0], tab_hash)
        while True:
            # 判断当前窗口是否包含所有T
            if not self.less_zero(tab_hash.values()):
                # 包含所有，移动左指针，直到不包含所有
                val_left = S[left]
                val_s = tab_hash.get(val_left)
                left += 1
                if val_s is not None:   # 左指针数据存在T中
                    tab_hash[val_left] -= 1
                    if self.less_zero(tab_hash.values()):   # 不包含所有
                        min_str = S[left - 1:right + 1]
                        if res == '':
                            res = min_str
                        elif len(min_str) < len(res):
                            res = min_str
                if left >= len(S):
                    break
                continue    # 不移动右指针
            # 不包含所有，继续移动右指针
            right += 1
            if right >= len(S):
                break
            tab_hash = self.exist_add(S[right], tab_hash)
        return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
import collections
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        ret = ''
        if len(S) < len(T):
            return ''
        if len(S) == len(T):
            if S == T:
                return S
            else:
                return ''
        # write code here
        left, right = 0, 0
        minlen = 999999
        need = dict(collections.Counter(T))
        window = dict()
        match = 0
        while right < len(S):
            c1 = S[right]
            if need.get(c1):
                window.setdefault(c1, 0)
                window[c1] += 1
                if window[c1] == need[c1]:
                    match += 1
            right += 1
            while match == len(need):
                if right - left < minlen:
                    minlen = right - left
                    print(minlen)
                    ret = S[left:right]
                c2 = S[left]
                if need.get(c2):
                    window.setdefault(c2, 0)
                    window[c2] -= 1
                    if window[c2] < need[c2]:
                        match -= 1
                left += 1
        return ret

import collections
class Solution:
    def com_dic(self,dict1: dict, dict2: dict):
        for key in dict2:
            if dict2[key] > dict1.get(key, 0):
                return False
        return True
    def minWindow(self, s: str, t: str) -> str:
        set_s = set(s)
        set_t = set(t)
        len_s = len(s)
        len_t = len(t)
        if len_s < len_t:
            return ""
        if not set_t.issubset(set_s):
            return ""
        i = 0
        result = []
        t_c = dict(collections.Counter(t))
        for j in range(len_s):
            while (
                set_t.issubset(s[i : j + 1])
                and len_t <= len(s[i : j + 1])
                and i <= j
                and Solution.com_dic(self,dict(collections.Counter(s[i : j + 1])), t_c)
            ):
                result.append(s[i : j + 1])
                i += 1
        result = sorted(result, key=lambda x: len(x))
        return "" if len(result) == 0 else result[0]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        m, M = -1, len(S)
        left, right = 0, 0
        sdict, tdict = {}, {}
        for i in T:
            if i in tdict.keys():
                tdict[i] = tdict[i] + 1
            else:
                tdict[i] = 1
        while right < len(S):
            if S[right] in tdict.keys():
                if S[right] in sdict.keys():
                    sdict[S[right]] = sdict[S[right]] + 1
                else:
                    sdict[S[right]] = 1
            else:
                right = right + 1
                continue
            right = right + 1
            flag = False
            for i in tdict.keys():
                if i in sdict.keys():
                    if tdict[i] > sdict[i]:
                        flag = True
                else:
                    flag = True
            if flag:
                continue
            while left < right:
                if M-m > right - left:
                    m, M = left, right
                tmp = S[left]
                left = left + 1
                if tmp in sdict.keys():
                    if sdict[tmp] > 1:
                        sdict[tmp] = sdict[tmp] - 1
                        if sdict[tmp] < tdict[tmp]:
                            break
                    else:
                        sdict.pop(tmp)
                        break
        if m == -1:
            return ''
        ret = S[m:M]
        return ret