力扣76.最小覆盖子串

本文主要是介绍力扣76.最小覆盖子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣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);}};
  

这篇关于力扣76.最小覆盖子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---