题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 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 的子串中,
因此没有符合条件的子字符串,返回空字符串。
思路分析
一道滑动窗口的题,不过归到了hard里,显然是有点弯弯绕绕在里面。
按步骤走先。
步骤一:
划定窗口的左右边界,left和right。
设置一个变量count来记录当前所需的字符。初始时count为字符串t的长度。
步骤二:
不断往右移动right,当count为0时,则表示当前窗口内的元素已经符合条件。
步骤三:
将left往右移动,减小窗口内的字符数量,将不必要的值扔掉,毕竟要求是最小的窗口长度嘛。
上述三步就是我一开始的思路,虽然我知道这道题肯定有点坑,没那么简单,但是还是按照上面这个思路写了一下,发现几个问题。
问题1:何时让count减一?
是碰到需要的字符就减1吗,显然不是,比如 s = ‘BECODEBANC’ t = ‘ABC’ 。count初始值为3。
可以看到,right不断从0开始往右走。当需要的字符A还没出现的时候,就已经出现了两次B和一次C了,这时候count已经为0。但此时窗口内的元素并不符合要求。
所以,需要一个辅助的哈希表来记录所需元素是否都已经符合要求了。
初始设置一个哈希表hs,遍历t来设置hs,本例中hs={‘A’: 1, ‘B’: 1, ‘C’: 1}。
right不断往右的过程中,遇到字符先判断hs里该值对应的value是否大于0,如果大于0,则表示是我们需要的值,此时再让count减一。
用上这个方法之后,再回头看刚才的例子。当出现第一个B的时候,他是我们需要的字符,则让hs[’ B ']-=1,计数器 ‘count-=1‘。此时哈希表中B字符对应的value就等于0了。当再次遇到第二个B的时候,哈希表中的B对应value为0,不满足大于0的要求,所以不减count。
问题2: 当count为0时,立即记录窗口长度值吗?
在第二步的时候,count为0了,虽然此时窗口内的长度已经覆盖了t,但是并不是要立即记录窗口的长度值。 比如 s = ‘BECODEBANC’ t = ‘ABC’
假设现在的left指向第一个B,也就是0号位置,right不断向右走,走到倒数第三个位置的A,此时窗口内包含ABC三个元素,这时候count=0了。但可以发现,窗口内含有两个B,左边的B是不必要的值。
为了减小窗口的长度符合题意,则尽量将左边界往右移动,缩短窗口长度。
此时就遇到了问题3.
问题3,:左边界left缩短的终止条件是什么?
从问题2可以看到,缩短左边界是在每一次记录前要做的事。
在解决这个问题之前,必须重申,hs表里记录的是每一个元素需要的次数。
比如 {‘A’: 1, ‘B’: 1, ‘C’: 1}),则表示A需要1次,B需要1次,C需要1。
如果{‘A’: 0。,C=‘-1’} 则表示A已经不需要了,刚好,而C多余一个。
hs表里记录的是每一个元素需要的次数!!!
hs表里记录的是每一个元素需要的次数!!!
hs表里记录的是每一个元素需要的次数!!!
牢记上面这句话。
所以在判断何时终止左边界的时候就非常好想了,如果碰到左边界的值在哈希表中的value为0了,则说明这个左边界的值是必须需要的,此时终止。
这时候left和right的窗口内所有元素都是需要的,此时记录,更新窗口的最短长度。文章来源:https://www.toymoban.com/news/detail-477339.html
问题4:非条件值是否会影响left的终止条件?
本例中必须条件值是ABC,还有一个非条件值,DEON四个。
在程序运行过程中,非条件值也会被加入到哈希表中,那么DEON这四个非条件值会影响left的终止吗。
显然不会,因为哈希表本身就是记录所需元素的个数的,一开始,那些不需要的元素是没有进行初始化的,或者说初始化为0,遇到一个则变成-1。再看一遍那句话hs表里记录的是每一个元素需要的次数!!!秒懂!!结束。文章来源地址https://www.toymoban.com/news/detail-477339.html
完整代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
import collections
hs = collections.defaultdict(int)
for i in t: # 先初始化t字符到哈希表中
hs[i] +=1
count = len(t)
res = [0,99999]
left = 0
right = 0
while right<len(s):
if hs[s[right]]>0: # 若哈希表中当前value大于0,则只可能是我们需要的字符
count-=1
hs[s[right]]-=1
if count == 0:
while True: # 去掉左边多余的值
if hs[s[left]] == 0:
break
hs[s[left]] +=1
left +=1
if right-left < res[1] - res[0]: # 记录当前最大值
res[0], res[1] = left,right
# 这时候的字符串状态是满足条件的,要移动左指针让他继续往右移动
hs[s[left]] +=1
count +=1
left+=1
right +=1
return ''if res[1]==99999 else s[res[0]:res[1]+1]
到了这里,关于leetcode(力扣) 76. 最小覆盖子串 (滑动窗口,超详细问答版解析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!