Day64 | 灵神 | 滑动窗口：最小覆盖子串

76.最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

总的来说笔者自己很难做出这道题，基本都是参考了灵神的题解，下面记录自己的理解和踩坑记录

思路

思路还是好想的，就和之前的滑动窗口题目一样，固定右端点，遍历右端点，寻找左指针的收缩条件，好想的地方在于收缩条件无比的简单，就是看[l,r]内是否涵盖了t中的所有的字符即可，如果涵盖了，我们就收缩左指针，寻找更小的子串，如果不再涵盖的话，那说明已经不满足收缩条件，我们就继续往后遍历右指针，看看新的[l,r]内是否可以涵盖t的所有字符

可能产生的疑惑

我在固定r的时候，把l收缩到一个位置了，那么当固定r+1时，需要重新把l置为0吗？

其实是不需要的，固定r的时候我们如果找到了一个最小的区间[l,r]是满足条件的，那么[l,r+1]肯定是大于[l,r]的，所以没必要重新把l置为0

笔者认为的本题难点

困难题还是困难题呀，考察一个人的综合素养，反正是给笔者卡住了

1.如何知道我当前的[l,r]区间涵盖了t的所有字符？

笔者第一想法是用哈希表统计t的所有字符数量，另一个哈希表统计[l,r]的所有字符数量，然后再遍历一遍[l,r]，把哈希表中的数都给减掉，如果t的字符的哈希值最后都大于0那就说明是涵盖了，可是这个代码实现真的太麻烦了，时间复杂度我也不敢想（现在想想这个想法还有点可笑）

就去参考了灵神的，灵神也是用两个哈希表，灵神是统计完t的字符数量之后，把大写英文和小写英文遍历一遍，然后比较同一个字符的两个哈希表的数值，如果s的哈希表的所有的大小写字符都比t的哈希表的数值大，那就说明肯定涵盖了所有的t的字符。

只需要比大小就好，不需要加加减减的。这个方法要记住。

2.内存超出限制

看下方的踩坑记录即可

3.我的res一开始是空串，如果最后还是空串，我如何得知那么是没有答案，还是有答案但是没有更新呢？

看下方的踩坑记录即可

4.更新答案的条件该如何写呢？

用左右两个端点res_l,res_r记录最后的答案，如果[l,r]区间长度小于[res_l,res_r]我们就去更新res_l和res_r

踩坑记录

1.超出内存限制

我一开始是用res存储最后的答案，然后在循环过程中去更新答案。但是如果s很大，每次循环中的res也会很大，导致内存超出了限制

只需要保存答案子串的左右端点即可，然后返回时使用

2.我的res一开始是空串，如果最后还是空串，那么可能是没有答案，也有可能是答案但是没有更新

下面是笔者遇到的有答案但是没有更新的例子

前面说到，我是用res存储答案，后面改为了用res_l,res_r存储左右端点，一开始我的初始化是

1
res_l=0,res_r=s.size()-1;

可是这样就出现了一个问题，当

1
s="a",t="a"

的时候，就会发现，我的[l,r]和[res_l,和res_r]竟然是一样的，而更新答案的条件是

1
r-l<res_r-res_l

那么就不会更新答案了

要解决这个问题，只需要把res_l初始化为-1，然后看最后res_l是不是-1即可，是-1就没更新，返回空串，不是-1就更新了，返回[res_l,res_r]区间的子串即可

下面是超出内存限制和没有修改前更新答案条件的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool is_covered(vector<int> s,vector<int> t)
    {
        for(int i='A';i<='Z';i++)
            if(s[i]<t[i])
                return false;
        for(int i='a';i<='z';i++)
            if(s[i]<t[i])
                return false;
        return true;
    }
    string minWindow(string s, string t) {
        string res;
        int l=0;
        vector<int> v_s(128,0);
        vector<int> v_t(128,0);
        for(char c:t)
            v_t[c]++;
        for(int i=0;i<s.size();i++)
        {
            v_s[s[i]]++;
            while(is_covered(v_s,v_t))
            {
                if(res.size()==0||res.size()>i-l+1)
                    res=string(s.begin()+l,s.begin()+i+1);
                v_s[s[l]]--;
                l++;
            }
        }
        return res;
    }
};

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    bool is_covered(int s[],int t[])
    {
        for(int i='A';i<='Z';i++)
            if(s[i]<t[i])
                return false;
        for(int i='a';i<='z';i++)
            if(s[i]<t[i])
                return false;
        return true;
    }
    string minWindow(string s, string t) {
        int l=0;
        string res;
        int res_l=-1,res_r=s.size()-1;
        int v_s[128]{};
        int v_t[128]{};
        for(char c:t)
            v_t[c]++;
        for(int i=0;i<s.size();i++)
        {
            v_s[s[i]]++;
            while(is_covered(v_s,v_t))
            {
                if(i-l<res_r-res_l+1)
                {
                    res_r=i;
                    res_l=l;
                }
                v_s[s[l]]--;
                l++;
            }
        }
        return res_l==-1?"":s.substr(res_l,res_r-res_l+1);
    }
};