每日一题：LeetCode-76. 最小覆盖子串

作者：半亩房顶

2023-12-04
北京
本文字数：1635 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-window-substring/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个字符串 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 的子串中，因此没有符合条件的子字符串，返回空字符串。

复制代码

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思路

最开始看到题目，想的就是哈希表存储字符计数，然后每次增加一个字符就看下是否满足，那么刚刚满足所有字符时就是最小覆盖子串了，不过当看到第一条注意以及示例时，意识到如果是字符存在重复的话，那么就有可能刚刚满足时并不是最小的覆盖子串。

但是，基于思路不能轻易浪费的念头，继续顺着这个思路思考下：

如果此时覆盖子串并不是最短的，如果收缩？
如果需要收缩，右边界也就是遍历方向，如果遍历方向上满足了覆盖子串需求时，会立即触发判断，所以右边界并不需要收缩，反证法易得结论
左边界如果收缩？

对于如下例子来说，刚刚找到第一个覆盖子串时，其实可以让L指针继续右移到c处，此时才是最小覆盖子串，所以左边界收缩的特点就是找到覆盖子串后，逐步右移L，并同步的修改覆盖子串的字符计数信息，只要继续满足那就有可能会更新最小覆盖子串的长度，同时记录最小覆盖子串的位置坐标信息就好了

能否简化操作。比如字符串中常见的，找到一个最小覆盖子串后，移动L到R位置，减少L的遍历次数？
不可，因为在移动过程中，可能错过覆盖子串，比如上图中，如果R右移两个位置后，其实L在第一个b的位置才是最小覆盖子串，但是如果移动L到R位置，将会错过此结果

至此，上代码，细节在备注里了~

代码

func minWindow(s string, t string) string {    // 用哈希表存储子串字符及对应个数    childCountMap := make(map[byte]int, 0)    for _, b := range t {        childCountMap[byte(b)]++    }
    // 另用一个哈希表存储父串字符及对应个数    countMap := make(map[byte]int, len(childCountMap))    // 需要一个变量来记录最短长度方便比较；另需要两个变量来记录最短长度对应的位置    resStartP, resEndP, minLen := -1, -1, math.MaxInt32    // 记录s中覆盖t的子串的左边界，通过移动此位置来寻找最小的子串的左边界    l := 0    // s中覆盖t的子串的右边界，其实就是最开始满足覆盖t时遍历到的s的位置    for r, b := range s {        countMap[byte(b)]++        for checkChild(countMap, childCountMap) && l <= r {            // 注意长度是相减后+1            if r-l+1 < minLen {                minLen = r - l + 1                // 这里记录的是起止下标，最终结果返回时候要注意                // 需要截取的子串应该放的下标是[resStartP, resEndP+1]                resStartP, resEndP = l, r            }            countMap[s[l]]--            l++        }    }    // 没有出现过覆盖子串，那就返回空    if resStartP == -1 {        return ""    }    return s[resStartP : resEndP+1]}
func checkChild(countMap, childCountMap map[byte]int) bool {    for k, v := range childCountMap {        if countMap[k] < v {            return false        }    }    return true}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/548e8bb226300fbfe9fcdda2d】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-76. 最小覆盖子串

题目

思路

代码

半亩房顶

评论