力扣_字符串6—最小覆盖字串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

示例 ：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

方法

• 滑动窗口
  

代码

class Solution {
public:
    bool check(map<char, int>& maps){
        for(auto it : maps){
            if(it.second > 0){
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        int n = s.size();
        int n1 = t.size();
        map<char, int> maps;
        for(int i = 0; i < n1; i++){
            maps[t[i]]++;
        }
        int pl = 0, pr = 0;
        int pl_ret = 0;
        int ret = n;
        bool flag = false;
        while(pr <= n){
            if(!check(maps)){
                if(maps.find(s[pr]) != maps.end())
                    maps[s[pr]]--;
                pr++;
            }
            else{
                if(pr-pl <= ret){
                    flag = true;
                    ret = pr-pl;
                    pl_ret = pl;
                }
                if(maps.find(s[pl]) != maps.end())
                    maps[s[pl]]++;
                pl++;
            }
        }
        if(flag)
            return s.substr(pl_ret, ret);
        else
            return "";
    }
};
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
38
39
40
41
42
43
44