最小覆盖子串

问题简述

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

最小覆盖子串_牛客题霸_牛客网

思路：滑动窗口

• 应用模板比较复杂的一题；

滑动窗口模板

l = r = 0  # 初始化 [l, r] 闭区间
while r < N:
    # 更新窗口
    while check():  # 满足要求进入循环，不满足退出
        # 更新答案
        l += 1  # 移动左边界
    r += 1  # 移动右边界

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        
        from collections import Counter, defaultdict
        
        l, r = 0, 0
        N = len(S)
        ret = S  # 初始化为最大的可能，但是注意，可能有无结果的情况，所以还需要一个变量记录答案是否存在
        flag = -1  # 记录是否出现过匹配串，避免无答案的情况
        need = Counter(T)
        used = defaultdict(int)
        
        def check():  # 检验是否满足情况
            for k, v in need.items():
                if k not in used or used[k] < need[k]:
                    return False
            return True
        
        while r < N:
            used[S[r]] += 1
            while check():
                flag = 1
                if r - l < len(ret):
                    ret = S[l: r + 1]
                used[S[l]] -= 1
                l += 1
            r += 1
        
        return ret if flag != -1 else ''