力扣76.最小覆盖子串

力扣76.最小覆盖子串

• 用哈希表记录每个字母出现次数
  
  
  
  • 枚举右端点 判断是否能全覆盖
    
  • 如果可以 而且更短 就更新
    
    
    
    • j ++缩小区间再判断
      
    
    
  
  
• 1.   class Solution {
  2.       bool is_covered(int cnt_s[], int cnt_t[]) {
  3.           for (int i = 'A'; i <= 'Z'; i++) {
  4.               if (cnt_s[i] < cnt_t[i]) {
  5.                   return false;
  6.               }
  7.           }
  8.           for (int i = 'a'; i <= 'z'; i++) {
  9.               if (cnt_s[i] < cnt_t[i]) {
  10.                   return false;
  11.               }
  12.           }
  13.           return true;
  14.       }
  15.   public:
  16.       string minWindow(string s, string t) {
  17.           int cnt_s[128]{}, cnt_t[128]{};
  18.           int n = s.size(),res=n;
  19.           int st=-1,ed=n;
  20.           for(auto c:t)
  21.               cnt_t[c] ++;
  22.           for(int i=0,j=0;i<n;i++)
  23.           {
  24.               cnt_s[s[i]] ++;
  25.               while(is_covered(cnt_s,cnt_t))
  26.               {
  27.                   if(i - j < ed - st)
  28.                   {
  29.                       ed = i;
  30.                       st = j;
  31.                   }
  32.                   cnt_s[s[j++]] -- ;
  33.               }
  34.           }
  35.           return st < 0 ? "" : s.substr(st, ed -  st + 1);
  36.       }
  37.   };

  复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。