解法1
class Solution{
bool is_covered(unordered_map<int,int>&cnt_s,unordered_map<int,int>&cnt_t){for(int i='A';i<='Z';i++){if(cnt_s[i]<cnt_t[i])return false;}for(int i='a';i<='z';i++){if(cnt_s[i]<cnt_t[i])return false;}return true;
} //检查这个s是不是可以覆盖t
public:
string minWindow(string s, string t) {unordered_map<int,int>cnt_s,cnt_t;int left=0,m=s.length(),temp_left=-1,temp_right=m,ans=INT_MAX;for(char i:t)cnt_t[i]++;for(int i=0;i<m;i++){cnt_s[s[i]]++;while(is_covered(cnt_s,cnt_t)){if(i-left+1<temp_right-temp_left+1){temp_left=left;temp_right=i;}cnt_s[s[left]]--;left++;}}return (temp_left<0?"":s.substr(temp_left,temp_right-temp_left+1));
}
};
解法2
class Solution2 {bool is_covered(int cnt_s[], int cnt_t[]) {for (int i = 'A'; i <= 'Z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}return true;}public:string minWindow(string s, string t) {int cnt_s[128]{}; // s 子串字母的出现次数int cnt_t[128]{}; // t 中字母的出现次数
//用数组更快for (char c : t) {cnt_t[c]++;}int m = s.size();int ans_left = -1, ans_right = m;int left = 0;for (int right = 0; right < m; right++) { // 移动子串右端点cnt_s[s[right]]++; // 右端点字母移入子串while (is_covered(cnt_s, cnt_t)) { // 涵盖if (right - left < ans_right - ans_left) { // 找到更短的子串ans_left = left; // 记录此时的左右端点ans_right = right;}cnt_s[s[left]]--; // 左端点字母移出子串left++;}}return ans_left < 0 ? "" : s.substr(ans_left, ans_right - ans_left + 1);}
};
解法2优化
这个优化的方案是，上一个解法每次都要花费时间去看是不是is_covered,也就是O（52），我们可以直接维护一个less，表示t中没有出现过的字符的种类
class Solution3{
public:string minWindow(string s,string t){int cnt[128]{};int less=0,m=s.length(),temp_left=-1,temp_right=m,left=0;for(char&i:t){if(cnt[i]==0)less++;cnt[i]++;}for(int right=0;right<m;right++){cnt[s[right]]--;//如果这个字符在t中没有出现过的话，那么就会变成-1，因为刚开始大家都是0if(cnt[s[right]]==0)less--;//如果这个字母的数量现在跟t中的一样的话，那么代表种类的less就减去1，当less等于1的时候，代表t中的字母已经被覆盖了while(less==0){if(right-left+1<temp_right-temp_left+1){temp_right=right;temp_left=left;}if(cnt[s[left]]==0)less++;//如果这个cnt==0说明是t中的字符，这个字符现在//出这个窗口了cnt[s[left]]++;left++;}}return (temp_left<0?"":s.substr(temp_left,temp_right-temp_left+1));}
};