力扣-最小覆盖子串
76. 最小覆盖子串 - 力扣(LeetCode)
给定一个字符串s,和目标字符串t,需要找出s中包含t中所有字符且长度最小子串,输出这个子串
滑动窗口,初始时左右指针都指向s的第一个字符,对于每个遍历到的窗口,判断当前窗口是否包含了t中所需要的所有字符,不是的话就移动右指针,是的话就移动左指针。
怎么判断当前窗口是否包含了t中所需要的字符?
可以定义一个distance这样的int变量,当移动右指针后,如果此时右指针指向的字符在当前窗口中的个数严格小于t中所需要的个数,那么distance++。
在移动左指针前,如果此时左指针指向的字符在当前窗口中的个数等于t中所需要的个数,那么distance--。
distance等于t中所含字符数量时,就说明当前窗口是一个符合条件的子串
class Solution {
public String minWindow(String s, String t) {
int ans=1000000;
String ansString="";
int [] target=new int[200];
int [] window=new int[200];
int ansCount=0;
for (int i = 0; i <t.length() ; i++) {
target[t.charAt(i)]++;
ansCount++;
}
int distance=0;
for (int l=0,r=0; r <s.length() ; r++) {
char x =s.charAt(r);
if(window[x]<target[x]){
distance++;
}
window[x]++;
int f=0;
while(distance==ansCount){
f=1;
// if(ans>r-l+1){
// ans =r-l+1;
// ansString=s.substring(l,r+1);
// }
if( window[s.charAt(l)]==target[s.charAt(l)]){
distance--;
}
window[s.charAt(l)]--;
l++;
}
//出循环说明distance不满足anscount了
if(f==1&&ans>r-l+2){
f=0;
ans =r-l+2;
ansString=s.substring(l-1,r+1);
}
}
return ansString;
}
}