2022-4-25 滑动窗口

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

 1 class Solution {
 2     public String minWindow(String s, String t) {
 3         int l=0,r=0,len=100001,point=0;
 4         Map maps=new HashMap<>();
 5         Map mapt=new HashMap<>();
 6         for (int i=0;i) {
 7             mapt.put(t.charAt(i),mapt.getOrDefault(t.charAt(i),0)+1);
 8         }
 9         while (r<s.length()){
10             char c=s.charAt(r);
11             maps.put(c,maps.getOrDefault(c,0)+1);
12             while (check(maps,mapt)){
13                 if (r-l+1<len){
14                     len=r-l+1;
15                     point=l;
16                 }
17                 maps.put(s.charAt(l),maps.get(s.charAt(l))-1);
18                 l++;
19             }
20             r++;
21         }
22         if (len==100001) return "";
23         else return s.substring(point,point+len);
24     }
25 
26 
27 
28     public boolean check(Map s,Map t){
29         for (char key:t.keySet()){
30             if (!s.containsKey(key)||s.get(key)return false;
31         }
32         return true;
33     }
34 }

思路：滑动窗口，数组效率应该比map更高。

 1 class Solution {
 2     public String minWindow(String s, String t) {
 3         int[] tmap=new int[52];
 4         int[] smap=new int[52];
 5         int l=0,r=0;
 6         for (int i=0;i){
 7             //前面26个小写，后面大写
 8             if ('a'<=t.charAt(i)) tmap[t.charAt(i)-'a'+26]++;
 9             else tmap[t.charAt(i)-'A']++;
10         }
11         int max=100001,index=-1;
12         while (r<s.length()){
13             if ('a'<=s.charAt(r)) smap[s.charAt(r)-'a'+26]++;
14             else smap[s.charAt(r)-'A']++;
15             while (check(tmap,smap)){
16                 if (r-l+1<max) {
17                     index=l;
18                     max=r-l+1;
19                 }
20                 if ('a'<=s.charAt(l)) smap[s.charAt(l)-'a'+26]--;
21                 else smap[s.charAt(l)-'A']--;
22                 l++;
23             }
24             r++;
25         }
26         
27         return max!=100001?s.substring(index,index+max):"";
28     }
29 
30     public boolean check(int[] a,int[] b){
31         for (int i=0;i){
32             if (a[i]>b[i]) return false;
33         }
34         return true;
35     }
36 }