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 字符串末尾。缩小窗口期间要更新子串的长度(因为题目要求的就是最小子串)
欢迎关注微信公众号《书所集录》