题目：
    76.最小覆盖子串
    image.png

    思路：
    滑动窗口。关键在于判断窗口中的字符串是否包含T中所有字母
    from collections import Counter

    1. class Solution:
    2.     def minWindow(self, s: str, t: str) -> str:
    3.         def is_contained(window, t):
    4.             # dict
    5.             window = dict(window)
    6.             t = dict(t)
    7.             for t_key, t_val in t.items():
    8.                 if window.__contains__(t_key):
    9.                     if window[t_key] < t_val:
    10.                         return False
    11.                 else:
    12.                     return False
    13.             return True
    16.         t = Counter(t)
    17.         left = right = 0
    18.         window = {}
    19.         min_substr = list(s)
    20.         while right < len(s):
    21.             window[s[right]] = window.get(s[right], 0) + 1
    22.             while is_contained(window, t):
    23.                 if right-left+1 <= len(min_substr):
    24.                     min_substr = s[left:right+1]
    25.                 window[s[left]] -= 1
    26.                 left += 1
    27.             right += 1
    28.         return min_substr if type(min_substr) is str else ''

    超时做法

    1. class Solution:
    2.     def minWindow(self, s: str, t: str) -> str:
    3.         def is_contained(sub_s, t):
    4.             sub_s = list(sub_s)
    5.             for c in t:
    6.                 if c in sub_s[:]:
    7.                     sub_s.remove(c)
    8.                 else:
    9.                     return False
    10.             else:
    11.                 return True
    15.         left = 0
    16.         right = 0
    17.         min_substr = s
    18.         Flag = False
    20.         while right < len(s):
    21.             right += 1
    23.             while is_contained(s[left:right], t) and left < right:
    24.                 print('ok')
    25.                 if len(s[left:right]) <= len(min_substr):
    26.                     print('fuzhi')
    27.                     min_substr = s[left:right]
    28.                     Flag = True
    29.                     print(min_substr)
    30.                 left += 1
    31.         return min_substr if Flag else ''

    别人简洁的代码

    1. class Solution:
    2.     def minWindow(self, s: str, t: str) -> str:
    3.         ans=''
    4.         l=0
    5.         minn=99999
    6.         d=Counter(t)
    7.         dd=defaultdict(int)
    8.         for i in range(len(s)):
    9.             dd[s[i]]+=1
    10.             while involve(d,dd):
    11.                 if i-l<minn:
    12.                     minn=i-l
    13.                     ans=s[l:i+1]
    14.                 dd[s[l]]-=1
    15.                 l+=1
    16.         return ans
    17. def involve(a,b):
    18.     for k,v in a.items():
    19.         if k not in b or b[k]<v:
    20.             return False
    21.     return True
    23. 作者：cpf_china
    24. 链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/python3-by-cpf_china-10/
    25. 来源：力扣（LeetCode）
    26. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。