Leetcode76:最小覆盖子串

基本思路是先统计字符子串t中各个字符的个数need,然后通过滑动窗口来对字符串进行处理,当窗口中出现t中的字符时need-1。当need=0时,移动左边窗口,此时移除的字符若是t中的且该字符的计数>0(说明该窗口中还没包含足够的当前字符)时,need+1。

import collections
def minWindow(s: str, t: str) -> str:  #s大字符串 t小字符串
    cnt = collections.Counter(t)
    left = 0
    need = len(t) #用来记录t中还存在的字符个数
    min_lens = len(s)+1
    start,end = 0,0
    for i,x in enumerate(s):
        if x in cnt:  #这里主要是让窗口包含t中所有的字符 出现所需字符,数量就减少    如果滑到的字符在t里面
            if cnt[x] >0:  #如果滑到的字符在t里面,且所需个数>0
                need -= 1  #那么所需字符串个数-1
            cnt[x] -= 1    #重点:只要当前的字符在t里面,不管他还有几个需求,个数都会-1。这样就会出现字符个数为负数的情况
        while need == 0:   #这里主要是让左边窗口不断滑动
            if i-left+1 < min_lens:
                min_lens = i - left + 1
                start,end = left,i+1
            if s[left] in cnt:
                if cnt[s[left]] >= 0: #如果左边滑出去的字符个数在counter中>0,说明此时的窗口中包含该字符的数量还不够
                    need += 1
                cnt[s[left]] += 1 #只要字符是t中需要的,滑出去了数量就要+1
            left += 1
    return s[start:end]

leetcode76:最小覆盖子串