力扣76.最小覆盖子串
-
用哈希表记录每个字母出现次数
- 枚举右端点 判断是否能全覆盖
- 如果可以 并且更短 就更新
- j ++缩小区间再判断
-
class Solution {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]{}, cnt_t[128]{};int n = s.size(),res=n;int st=-1,ed=n;for(auto c:t)cnt_t[c] ++;for(int i=0,j=0;i<n;i++){cnt_s[s[i]] ++;while(is_covered(cnt_s,cnt_t)){if(i - j < ed - st){ed = i;st = j;}cnt_s[s[j++]] -- ;}}return st < 0 ? "" : s.substr(st, ed - st + 1);}};