【优选算法 — 滑动窗口】串联所有单词的子串 & 最小覆盖子串

XiaoLeisj

2563人浏览 · 2024-11-17 22:16:56

XiaoLeisj · 2024-11-17 22:16:56 发布

串联所有单词的子串

题目描述

题目解析

算法原理

以示例一为例，一定要记得，words中的每一个字符串长度相同，所以我们可以根据 words 中的每一个字符串的长度length，将 s 这个字符串以 length 个为一组来进行划分。

通过这样的转换，就变成了上一篇优选算法的问题：“找出字符串中所有字母异位词”

所以这道题的示例一：

解法：滑动窗口 + 哈希表

两道题不同之处：

1. 哈希表

在438题中，我们是通过数组来模拟哈希表，因为哈希表中的每一个元素 key 是一个个字符；

但是在这题是一个个字符串，映射关系是 HashMap<String, int >，表示字符串及出现次数；

2. left 和 right 指针的移动

刚开始，我们的left 和 right 两个指针，都指向 s 字符串的第一个元素：

但是我们在每次入窗口操作时，都要把三个字符组成的字符串划入哈希表中，所以 left，right 移动的步长，是 words 中字符串元素的长度。

在这题中，我们移动 right ，让第二个字符串进入哈希表：

3. 滑动窗口的执行次数

因为我们是把三个字符看作是一个字符，所以划分方法有很多种，如下面的这三种：

因此滑动窗口的次数，就是能列举出来的上图的三种情况;
因为上面三种情况，分别以 s 的第一，第二，第三个字符为起点，把长度3的字符串看成一个字符；
那接下来就是以第四个字符为起点，那这种情况就变回了上面的第一种划分方法，只是少了第一个字符串 "bar" ;
同理，后面再以第五，第六，第七个 .......s 字符串的字符为起点，结果都能合并为上面三种划分情况

编写代码

定义哈希表 hash1，用来保存 wors 中所有单词（字符串元素）的频次

把 words 的每一个字符串元素存入 hash1

滑动窗口的执行次数（外层 for 循环）

完善滑动窗口的主逻辑；

left 和 right 指针不是从0开始，而是从 i 开始，如果 left 和 right 从0开始，就会重新遍历很多已经遍历过的字符串（内层 for 循环）；

count 用来记录有效字符串的个数：

注意，求数组长度和字符串长度，分别使用的是 length 和 length()

接下来有一个小细节：

所以对于上面的这两种情况，right 指针能到的极限位置就是上面两种情况 right 指向的位置，只要 right 到达这个位置，就不能再往后移动了，所以我们修改一下代码：

定义一个哈希表 hash2，保存窗口内所有单词的频次；

进窗口，维护 count；此时，input 存的字符串，就是要进窗口的字符串：

进窗口

方法一：

执行用时

方法二

执行用时

进完窗口，要看一下 key 为 input 的哈希元素，如果 hash2 的 val 是否小于 hash1 ，则 count++

但是有一个问题，如果在 hash1 中并没有 key 为 input 的元素，则会报错；
因为调用哈希表中的 get(key)，如果对应的 val 为0，则代表不存在这个映射，get() 此时返回 null
因此我们修改一下代码（如果 hash1 中有 key 为 input 的元素，返回该元素 val，否则返回0；）

判断是否需要出窗口：

注意 m = words.length，表示单词的个数，len 表示 words 中的单词长度。len*m 表示窗口长度。

(如果 right - left +1 > len*m，就出窗口，注意不是一个word 的长度，而是 words所有字符之和)

在 if 中，进行出窗口：

要在出窗口之前，维护 count，和上一次维护 count 的原理一样：

更新结果

完整代码

最小覆盖子串

题目解析

算法原理

每次以一个有效字符开始找，直到找完所有符合条件的字符，返回这个子串，然后开始以下一个有效字符为起点开始遍历：

我们用 hash1 存放 t 字符串的字符，hash1的每一个元素 key 为字符，val 为字符出现次数；

再以 hash2 存放 s 字符串的字符，只要遍历到 s 中的字符str，在hash2.get(str)<hash1.get(str)，则是有效字符，凑齐所有 t 中所有字符的字符串，就是一个有效字符串；

进出窗口的原理

那么为了不失一般性，我们以上图的抽象例子，来讲解 left 和 right 组成有效字符串后，left 和 right 会出现的情况：

left 向后移动一步，从字符 str1走到 str2：

情况一： left 删除的是无效字符

如果 str1 字符在 t 中也有，但是 hash2.get(str1)>hash1.get(str1)，则说明 str1并不是一个有效的字符，所以 right 不动；
right 不动，是因为新的 left 和 right 组成的字符串依旧是有效的字符串，left 删除的是一个无效字符；
但是 right 一回退，则一定会导致有效字符串变成无效字符串，因为 right 只有在 left 和 right 构成有效字符串才会停下来；

情况二：left 删除的是一个有效字符

left ++，如果导致新 left 和 right 组成的字符串从有效字符串，变成无效字符串；
则因为 left 删除的字符，导致 hash2.get(str1)<hash1.get(str1) ；
对于这种情况，只能让 left 停止 ++操作，让 right 往后 ++；
right 向后遍历，直到 right 遍历到 str1 的时候停止 ++，这时候 left 和 right 就是下一个有效字符串；

通过两种情况，发现 left 和 right 是同向移动的，所以使用滑动窗口解决该题；

解法：滑动窗口 + 哈希表（how 很重要，但是 why 最重要）

left = 0, right = 0;
进窗口（right ++，对应 key 的字符的 val++）；
判断是否出窗口（check(hash1,hash2)==true，说明窗口合法，才出窗口，这和前面的题目都不一样）
根据问题，找到合适的位置更新结果（更新起始位置 left 和最短长度，这样就能还原最短子串）
(程序执行到这里，窗口都是合法的，因此更新结果的步骤放到判断和出窗口之间）；
出窗口（left 出窗口，直到上面判断中的 check(hash1,hash2)==false）；

优化判断条件

上面的判断步骤，在每次循环时，都会对 hash1 和 hash2 进行判断，但是每次判断都需要遍历一次 hash1 和 hash2，这样太耗费时间了，我们可以优化判断这一过程；

我们可以定义一个变量 count，标记有效字符的种类，也就是只有一个种类的数量满足，count才会++（之前标记的都是有效字符的个数，只要字符个数是小于等于，就++）；

因为在串联所有单词的子串中，对于 hash1 和 hash2 中，元素的 val 必须是一一对应的，hash1的key对应的val有多少个，hash2就必须有多少个；

但是这道题：

所以，只要 left 和 right 组成的字符串对应的 hash2，每个 key 的 val 都大于等于 hash1，那么就是一个合法窗口，所以 count 标记的是有效字符的种类

count 只看当前字符是不是有效字符（当前字符val：hash2 >= hash1），而不看当前字符出现的次数，因此统计的是种类，为什么是种类，刚才已经解释过了，因为字符val不是一一对应的关系

进窗口之后，维护 count：只有两个字符出现的次数相等，count 才+1，否则会统计重复的；
出窗口之前，维护count：只有两个字符出现的次数相等，count 才-1，否则会统计重复的；
（因为 count 的出现，只服务于能成为有效字符串的指针移动，出现次数大于的时候，不影响有效字符串；出现次数小于的时候，会从有效字符串变成无效字符串；所以只有等于的时候，才+1）
判断条件（只有 count = 哈希表的元素种类hash.size() 时，而不是等于字符数量；count只有凑齐所有的有效字符，才更新结果，而不关系如何成为有效字符，出现次数多了也不算有效字符）

编写代码

这题可以用字符模拟哈希表(使用容器增删查改为O（1），但是消耗还是很大的)

定义模拟哈希表的两个数组，hash1用于统计 t 中字符的频次，hash2 统计窗口中字符的频次

找 Ascii 码是一个非常麻烦的过程，所以我们先以这两个字符串，生成字符数组；

统计字符串 t 中字符的频次

滑动窗口的主逻辑，注意，只有count统计的是字符种类，只有字符串在有效字符串和无效字符串相互转化的瞬间，才会更新 count；

入窗口

入窗口后，维护count，

定义 kind，用于计算 t字符串中的字符有多少种

更新结果（更新有效字符串的最小长度minlen ＆更新最小长度的有效字符串的起始位置 begin）

定义 minlen ，刚开始初始化为无穷大，不能初始化为0，因为minlen用于更新有效字符串的最短长度，初始化为0，后续后无法更新；

出窗口

出窗口之前先维护 count

设置返回值

注意，一定要把握好进出窗口维护count的时机，在进窗口和出窗口的过程中，只有有效字符种类对应的数目相等，才需要维护count；

right++ 的过程中，count++的条件，一定是 hash2[input] 从小于到等于 hash1[output] 的时候；
所以是在hash2[input]++ 之后，对应种类的数目是相等的；
所以是在hash2[input]++ 之后，才维护 count;

left++ 的过程中，count-- 的条件，一定是 hash2[output] 从等于到小于 hash1[output] 的时候；
所以是在hash2[output]-- 之前，对应种类的数目是相等的；
所以在 hash2[output]-- 之前，维护 count

完整代码

class Solution {
    public String minWindow(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kind = 0;
        for(char ch : t1){
            if(hash1[ch] == 0) kind++;
            hash1[ch]++;
        }
        int minlen = Integer.MAX_VALUE,begin = -1;

        for(int left = 0,right=0,count=0;right<s1.length;right++){

            char input = s1[right];
            hash2[input]++;

            if(hash2[input]==hash1[input])count++;

            while(count == kind){

                if(right - left + 1 < minlen){
                    minlen = right - left + 1;
                    begin = left;
                }
                
            char output = s1[left];

            if(hash1[output]==hash2[output])count--;

            hash2[output]--;
            left++;
            }          
        }
        if(begin == -1)return new String();
        else return s.substring(begin,begin + minlen);
    }
}