题目

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