python实现leetcode之76. 最小覆盖子串

解题思路

滑动窗口

第一步，统计一下t字符串里面每个字符出现的次数
第二步，滑动end指针，当begin与end之间能够完全包含t时，尽量滑动begin指针，直到再滑动就不能包围为止（最小覆盖）
第三步，比较当前窗口和之前保留的最小窗口，谁小保留谁
第四部，保留的最小窗口对应的字符子串就是ans

76. 最小覆盖子串

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ct = Counter(t)

        cs = {}
        begin = end = 0
        result = (begin, end)
        while end < len(s):
            char = s[end]
            if char in ct:
                cs[char] = cs.get(char, 0) + 1
                if cover(cs, ct):
                    # 后指针前进
                    while s[begin] not in ct or cs[s[begin]] > ct[s[begin]]:
                        if s[begin] in cs:
                            cs[s[begin]] -= 1
                        begin += 1
                    gap = result[1] - result[0]
                    if gap == 0 or gap > end+1-begin:
                        result = (begin, end+1)
            # 前指针前进
            end += 1
        return s[slice(*result)]


def cover(d1, d2):
    """
    d1覆盖d2吗？
    """
    for k, v in d2.items():
        if d1.get(k, 0) < v: return False
    return True