题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
思路
参考这里的代码：. - 力扣（LeetCode）
1）设置一个字典，保存t里每个字符出现的次数；用less保存key值的个数
2）在遍历s，修正字典里每个字符出现的次数
3）如果less为0，说明此时遍历的s，已经包含了t
4）计算最短的长度，保留首尾的下标
5）排掉最左边的元素，同时进行字典和less的还原
from collections import defaultdict
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
ansleft, ansright = -1, len(s)
cnt = defaultdict(int) # 括号里要有int
for i in t:
cnt[i]+=1
less = len(cnt)
left = 0
for right, ss in enumerate(s):
cnt[ss]-=1
if cnt[ss]==0:
less-=1
while less==0:
if right-left<ansright-ansleft:
ansleft,ansright=left,right
# 这块开始都是进行还原
x = s[left]
if cnt[x] == 0:
less+=1
cnt[x] += 1 # 这里是加1，还原
left +=1
return '' if ansleft<0 else s[ansleft:ansright+1]
if __name__ == '__main__':
s = Solution()
ss = "ADOBECODEBANC"
t = "ABC"
print(s.minWindow(ss, t))