LeetCode 76 最小覆盖子串
目录
本体是一道考察双指针的经典例题,非常值得深入研究和经常复习。
题目描述
原题链接如下: LeetCode 76 最小覆盖子串
题目大意
要在字符串 S 中找到包含 T 的所有字符的最短子串,同时注意 S 和 T 的字符都有可能重复。另外,子串的字符不必和 T 的字符顺序一致。
输入与输出
示例输入为:
|
|
对应输出为:
|
|
解题思路
遇到子串、子数组等问题一般会使用同向双指针构造滑动窗口来求解。 在本题中,我们通过在 S 上的滑动窗口能够得到一个不断变化的子串,如果子串的字符不包含 T 的全部字符则子串需要扩张,如果包含则需要收缩。每次收缩之前,都将得到一个包含 T 的所有字符的子串的长度,取它们的最小值就是本题答案。 另外,因为字符串比较中的一个字符串 T 是不变的,为了提高比较效率,可以使用计数桶编码 T 的所有字符。这样,在扩张时直接把新添加的子串字符对应的计数减一即可,收缩时则需要把减去的字符对应的计数加一。 至于子串是否包含 T 则不必通过统计计数桶是否全部不大于 0,而是通过维护一个匹配长度计数器来实现。在子串扩张时,如果新添加字符对应的计数减一后不小于 0,则表明又找到一个匹配对,匹配计数器加一;在收缩时,如果减少的字符对应的计数加一后大于 0,表明失去一个匹配对,匹配计数器减一。这样,只要匹配计数器等于 T 的长度就表明子串包含 T 的所有字符,即需要收缩。
注意:匹配计数器的值不会超过 T 的长度,因为如果子串中有更多的对应字符,其实就代表了字符对应的计数桶小于 0,此时匹配计数器不会有任何改变。
代码
|
|
本段代码中,虽然有两个嵌套的循环,但是要注意到这两个循环分别代表了子串的扩张和收缩,而不论是扩张还是收缩,最差情况都只会遍历一次 S 的所有字符,因而寻找子串的时间复杂度只有 O(|s|) 而已。