【leetcode 76】最小覆盖子串

滑动窗口问题，注意题干：返回 s 中涵盖 t 所有字符的最小子串

1. 记录t中的字符和频数
2. 使用滑动窗口遍历s，移动右窗口，同时记录窗口内的字符和频数
3. 当右窗口的字符频数等于所需的计数，cur_len加1
4. 当于满足t出现的字符个数，并且是目前的最小长度，更新结果（结果可以使用一个元组来记录）
5. 同时要右移动左边窗口，缩小窗口，并判断更新记录，直到右边窗口达到s的最后一个字符

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        l,r,ans,cur_len = 0,0,(float(‘inf‘),0,0),0
        s_d,t_d = {},{}
        for i in t: t_d[i] = t_d.get(i,0)+1
        while r<len(s):
            s_d[s[r]] = s_d.get(s[r],0) + 1
            if s_d[s[r]] == t_d.get(s[r],0): cur_len+=1
            while l<=r and len(t_d)==cur_len:
                if r-l+1 < ans[0]: ans = (r-l+1,l,r+1)
                s_d[s[l]]-=1
                if s_d[s[l]]<t_d.get(s[l],0): cur_len-=1
                l+=1
            r+=1
        return "" if ans[0]==float("inf") else s[ans[1]:ans[2]] 

【leetcode 76】最小覆盖子串

原文：https://www.cnblogs.com/wangshujaun/p/14044179.html