leetcode(力扣) 76. 最小覆盖子串 (滑动窗口,超详细问答版解析)

这篇具有很好参考价值的文章主要介绍了leetcode(力扣) 76. 最小覆盖子串 (滑动窗口,超详细问答版解析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

给你一个字符串 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的窗口内所有元素都是需要的,此时记录,更新窗口的最短长度。

问题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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣:76. 最小覆盖子串(Python3)

    给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,我们寻找的子字符串中该字符数量必须不少于  t  中该字符数量。 如果  s  中存在

    2024年02月11日
    浏览(36)
  • LeetCode----76. 最小覆盖子串

     题目 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 示例 1: 输入:s = “ADOBECODEBANC”, t = “ABC” 输出:“BANC” 解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、

    2024年02月06日
    浏览(44)
  • leetcode做题笔记76最小覆盖子串

    给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,我们寻找的子字符串中该字符数量必须不少于  t  中该字符数量。 如果  s  中存在

    2024年02月13日
    浏览(42)
  • 算法leetcode|76. 最小覆盖子串(rust重拳出击)

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 \\\"\\\" 。 注意 : 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是唯

    2024年02月10日
    浏览(62)
  • 【leetcode题解C++】51.N皇后 and 76.最小覆盖子串

    51. N皇后 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题  研究的是如何将  n  个皇后放置在  n×n  的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数  n  ,返回所有不同的  n   皇后问题  的解决方案。 每一种

    2024年02月20日
    浏览(42)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(69)
  • 76. 最小覆盖子串

    76. 最小覆盖子串 滑动窗口 两个 Integer 相等比较应该用 equals,而不是 ==。 一个 Integer 和一个 int 比较,Integer 会自动拆箱,可以用 ==。

    2024年02月06日
    浏览(39)
  • 【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(42)
  • 【Leetcode刷题-Python/C++】长度最小的子数组(滑动窗口)

    209.长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2023年04月08日
    浏览(41)
  • 【双指针】滑动窗口经典例题 力扣

    无重复的最长子串LC3 中等 题目链接 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 代码: 找到字符串中所有子母异位词LC438 中等 题目链接 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序

    2024年02月07日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包