LeetCode 76. 最小覆盖子串

LeetCode 76. 最小覆盖子串 | Python

76. 最小覆盖子串

题目来源：https://leetcode-cn.com/problems/minimum-window-substring

题目

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

解题思路

思路：滑动窗口

题目中要求，给定一个字符串 S，一个字符串 T，要在字符串 S 中找到包含 T 的所有字符的最小子串。

在这里，最主要的是找到最小子串。这一部分的内容就是要我们要维护更新的内容。

假如使用暴力解的话，代码大概如下：

for i in range(len(S)):
    for j in range(len(S)):
        if S[i:j] 包含 T 中所有字符：
            更新存储这部分的内容

在这里时间复杂度为 O(n^2)，不太理想。

本篇幅使用的是滑动窗口的思想。这里使用双指针，通过一静一动来达到搜索的目的。大致的思路如下：

首先初始化双指针，同时指向字符串 S 的开始位置（假设定义 left、right），那么 [left, right) 这个区间就是我们说的窗口，我们通过指针移动来控制窗口的大小。（上面区间是左闭右开，这里在开始定义指针指向索引为 0 的位置时，因为右开，所以定义开始这部分就是空区间）
接下来，我们先移动 right 指针（left 指针静止不动），让它不断扩大窗口的大小，直到窗口包含字符串 T 中所有字符
这时，停止移动 right 指针，移动 left 指针。这个时候，窗口就会缩小，当窗口的字符串不符合包含字符串 T 中的所有字符时，这个时候，停止移动 left 指针。在这里，从停止移动 right 指针，进而移动 left 指针时，要记得更新结果（因为要找到最小的子串）
现在只要不断重复上面第 2 步和第 3 步，直到 right 指针到字符串 S 末尾时，那么程序结束。

具体的实现代码如下。

代码实现

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        
        win = defaultdict(int)
        t_dict = defaultdict(int)
        for i in t:
            t_dict[i] += 1
        
        # 定义指针
        left = 0
        right = 0
        # 初始化最小长度
        min_len = float('inf')

        # chr_count 用以表示滑动窗口包含字符数
        chr_count = 0
        # 最小子串起始位置
        begin = 0
        # s 长度
        s_len = len(s)
        # t 长度
        t_len = len(t)

        while right < s_len:
            # 移动窗口，
            if t_dict[s[right]] == 0:
                right += 1
                continue
            # 滑动窗口包含 T 字符数，当超过 T 其中字符个数时不在增加
            if win[s[right]] < t_dict[s[right]]:
                chr_count += 1

            win[s[right]]+=1
            right+=1

            # 当窗口包含 T 所有的字符时，缩小窗口
            while chr_count == t_len:
                # 这里更新子串的起始位置和长度
                if right-left < min_len:
                    begin = left
                    min_len = right - left
                # 缩小窗口
                if t_dict[s[left]] == 0:
                    left += 1
                    continue
                # 这里表示出窗时，窗口所包含 T 的字符刚好等于 T 中字符的个数
                # 这个时候再移动，窗口就不满足包含 T 所有字符的条件
                # 这里 chr_count - 1 ，循环结束
                if win[s[left]] == t_dict[s[left]]:
                    chr_count -= 1

                win[s[left]]-=1
                left += 1

        return "" if min_len == float('inf') else s[begin:begin+min_len]

实现结果

总结

初始化指针，指向 S 字符串的开始位置
首先移动右指针，让窗口包含 T 字符串的所有字符
当满足上面的条件时，停止移动右指针，开始移动左指针，缩小窗口。当再移动左指针不满足包含 T 字符串所有字符时，停止移动左指针
循环上面的过程，直到右指针到达 S 字符串末尾。缩小窗口期间要更新子串的长度（因为题目要求的就是最小子串）

欢迎关注微信公众号《书所集录》