NC28 最小覆盖子串

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

描述：

给出两个字符串 S 和 T，要求在的时间复杂度内在 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个字符a，needCount=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。