题目
给你一个字符串 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 "";
}
};
