力扣：76. 最小覆盖子串（Python3）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣：76. 最小覆盖子串（Python3）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

如果 s 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例：

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"

解释：整个字符串 s 是最小覆盖子串。

示例 3：

输入：s = "a", t = "aa"
输出：""

解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

解法：

首先统计t中字频，存在dict_t；使用滑动窗口，初始化left=right=0；初始化返回子串的长度为100001，字串sub为空；取s中第1个字符存入dict_s，dict_t、dict_s都是Counter对象。

接着进入循环，使用滑动窗口的思想，更新left、right。如果dict_s和dict_t的交集是dict_t，说明此时滑动窗口中子串已覆盖t，然后就移动left，把dict_s中s[left]的值减1，试图缩小窗口大小，因为此时再增加right已没有意义，期间更新length、sub；如果交集不是dict_t，移动right，试图找到可以覆盖t的窗口，把dict_s中s[right]的值加1，如果right已经等于len(s)了，就跳出循环。

知识点：

1.关于字典交集：可以使用&计算两个字典交集。

2.collections.Counter()：创建一个计数器实例，也可以从list，tuple，dict，字符串等可迭代对象(iterable)创建。可以用来统计一个 python 列表、字符串、元组等可迭代对象中每个元素出现的次数，并返回一个字典。例如：c = collections.Counter(['a','a','b','b','c'])，输出c为{'a': 2, 'b': 2, 'c': 1}。在使用的时候当作字典使用，因为已经封装过，所以还不用考虑字典中的异常，比如取字典中不存在的键。文章来源地址https://www.toymoban.com/news/detail-676945.html

代码：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        dict_t = Counter(t)
        left = right = 0
        length = 100001
        sub = ''
        dict_s = Counter(s[0])
        while 1:
            if dict_s & dict_t == dict_t:
                if right - left + 1 < length:
                    length = right - left + 1
                    sub = s[left: right + 1]
                dict_s[s[left]] -= 1
                left += 1
            else:
                right += 1
                if right == len(s):
                    break
                else:
                    dict_s[s[right]] += 1
        return sub