最小覆盖子串

发表于 2020-01-28 分类于 leetcode 阅读次数：

最小覆盖子串（难度：困难）

1580195563488

方法：滑动窗口

算法

初始，left指针和right指针都指向s的第一个元素.
将 right指针右移，扩张窗口，直到得到一个可行窗口，亦即包含t的全部字母的窗口。
得到可行的窗口后，将left指针逐个右移，若得到的窗口依然可行，则更新最小窗口大小。
若窗口不再可行，则跳转至 2。

代码

from collections import defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        right = 0
        res = ""
        need = defaultdict(int)
        window = defaultdict(int)
        minLen = len(s)

        for i in t:
            need[i] += 1

        while right < len(s):
            window[s[right]] += 1
            while self.con(need,window):
                if len(s[left:right+1]) < minLen:
                    minLen = len(s[left:right+1])
                    res = s[left:right+1]
                window[s[left]] -= 1
                left += 1
            right += 1

        return res


    def con(self, need, window):
        for key in need.keys():
            if need[key] > window[key]:
                return False
        return True

复杂度

1580201292271

0%