LeetCode-76-最小覆盖子串-Python

45次阅读

共计 1759 个字符,预计需要花费 5 分钟才能阅读完成。

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 字符串末尾。缩小窗口期间要更新子串的长度(因为题目要求的就是最小子串)

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

正文完
 0