题解 | #最小覆盖子串#

最小覆盖子串

http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

NC28 最小覆盖子串

难度 通过率 时间限制 空间限制
较难 30.49% 1秒 64MB

描述:

给出两个字符串 ST,要求在的时间复杂度内在 S 中找出最短的包含 T 中所有字符的子串。

例如:

S ="XDOYEZODEYXNZ"
T ="XYZ"
找出的最短子串为"YXNZ".

注意:

  • 如果 S 中没有包含 T 中所有字符的子串,返回空字符串 ""
  • 满足条件的子串可能有很多,但是题目保证满足条件的最短的子串唯一。

示例1:
输入:

"XDOYEZODEYXNZ","XYZ"

返回值:

"YXNZ"

题解

滑动窗口

在jerry之前的算法题解中,也是有过滑动窗口解法的题目。

传送门:[Leetcode-3] 无重复字符的最长子串

  • 滑动窗口,是一种框架思维:
    • l,r表示滑动窗口的左边界右边界,通过改变l,r扩展收缩滑动窗口
  • 在这题目中可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串t的所有元素,记录下这个滑动窗口的大小slze = r-l+1,这些长度中的最小值就是要求的结果。
  • 主要分以下几个步骤:
  1. 从0开始,不断增加r使滑动窗口增大,直到窗口包含t的所有元素
  2. 从0开始,不断增加l使滑动窗口缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的大小,并保存最小值 mln
  3. l再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从步骤1开始执行,寻找新的满足条件的滑动窗口,如此反复,直到r超出了字符串S范围
  4. 判断滑动窗口是否包含t中的所有元素,这是将考虑的最关键的一部分!!!
  • 这里使用一个字典来记录t中的字符以及个数,还有所需个数
  • need[128]来记录t中字符,字符将以ASCII形式存储
  • needCount表示当前遍历下,满足t还需要的元素个数
  • need[97]=2表示t中需要2个字符aneedCount=3表示覆盖t还需要3个字符
  • 每当遍历到t中的字符,其对应的need[]应该-1
  • needCount==0时,则当前窗口覆盖了t中所有元素
  1. 其次关键是如何判断当前遍历的字符是不是多余的字符?要是多余,就可以移除。
  • 在这里,我对上面的字典need[]多加一步操作
  • 无论当前遍历字符在不在t中,都要在need-1
  • 要是多余字符,其对应的need[]一定是<0
  • 这样的目的:利用need[]正负来区分字符是否多余的还是有用的
  1. 最后一点,无论左边界还是右边界,在边界移动时候,要注意维护对应的参数。

算法手稿

滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        // l(left): 左边界
        // r(right): 右边界
        int l = 0, r = 0;
        // size=r-l+1: 滑动窗口的大小,默认值Integer.MAX_VALUE方便值交换
        int size = Integer.MAX_VALUE;
        // needCount: 当前遍历下,满足t还需要的元素个数,默认值、最大值是t.length,为0时表示滑动窗口内容覆盖了t中所有元素
        int needCount = t.length();
        // start: 记录有效滑动窗口的起始位置(左边界),方便后续查找对应的字串
        int start = 0;
        // 字典need: 记录滑动窗口中需要t中各个元素的数量
        // ASCII方式存储 [A-Z]:65-90  [a-z]:97-122
        // need[97]=2 表示t中需要2个a
        // t中对应字符的need[]必须>=0
        // 若need[]<0表示是个多余的字符
        int[] need = new int[128];
        // 根据t的内容,向字典need添加元素
        for (int i = 0; i < t.length(); i++)
            need[t.charAt(i)]++;
        // 循环条件,右边界不能溢出
        while (r < s.length()) {
            // 获取当前遍历的元素字符
            char c = s.charAt(r);
            // 若当前遍历字符是t中的内容,needCount需要-1
            if (need[c] > 0)
                needCount--;
            // 无论c在不在t中,都要在need中-1
            // 目的:利用正负来区分字符是否多余的还是有用的
            need[c]--;
            // needCount==0表示当前窗口满足t中所有元素
            if (needCount == 0) {
                // 判断左边界是否可以收缩
                // 如果l对应字符的need[]<0,表示是个多余的字符
                while (l < r && need[s.charAt(l)] < 0) {
                    // 在need[]中维护更新这个字符
                    need[s.charAt(l)]++;
                    // 左边界向右移,移除这个多余字符
                    l++;
                }
                // 判断是否更新有效滑动窗口的大小
                if (r - l + 1 < size) {
                    // 更新
                    size = r - l + 1;
                    // 记录有效滑动窗口的起始位置(左边界),方便查找对应的字串
                    start = l;
                }
                // 左边界对应的字符计数需要+1
                need[s.charAt(l)]++;
                // 重新维护左边界
                l++;
                // 重新维护当前的needCount
                needCount++;
            }
            // 右边界向右移,寻找下一满足条件的有效滑动窗口
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}

时间复杂度:。左右指针各自扫一遍字符串s,时间复杂度是

空间复杂度:。只用到一个字典用于记录的数组,长度128。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-18 16:22
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议