在串s中找出包含串t的所有字符的最小子串。
之前做了一些前缀和的题。想到用前缀和做：
统计第k个字符在第i个位置出现的个数:pre[i][k] .则可以用 前缀和遍历所有的子串组合。然后我们及时的减支
public String minWindow(String s, String t) {
char[] tCharArray = t.toCharArray();
char[] sCharArray = s.toCharArray();
int lenS = s.length();
int lenT = t.length();
HashMap<Character,Integer> indx = new HashMap<>();
int[] count = new int[lenT];
for(int i=0;i<lenT;i++){
if(!indx.containsKey(tCharArray[i]))
indx.put(tCharArray[i],i);
count[indx.get(tCharArray[i])]++;
}
int charIndx = 0;
int[][]precount = new int[lenS+1][lenT];
for(int i=0;i<lenS;i++){
for(int j=0;j<lenT;j++){
charIndx = indx.get(tCharArray[j]);
if(sCharArray[i]==tCharArray[j])
precount[i+1][charIndx]=precount[i][charIndx]+1;
else
precount[i+1][charIndx]=precount[i][charIndx];
}
}
for(int i=0;i<lenT;i++){
charIndx=indx.get(tCharArray[i]);
if(precount[lenS][charIndx]<count[charIndx]) return "";
}
int dis = Integer.MAX_VALUE;
int minLenJ=-1;
int minLenI=-1;
for(int i=0;i<lenS;i++){
for(int j=i+1;j<lenS+1;j++){
if(dis<(j-i)) break;
boolean containFlag = true;
for(int k=0;k<lenT;k++){
charIndx=indx.get(tCharArray[k]);
if(precount[j][charIndx]-precount[i][charIndx]<count[charIndx]){
containFlag=false;
break;
}
}
if(containFlag){
if(dis>(j-i)){
minLenI=i;
minLenJ=j;
dis=j-i;
}
}
}
}
if(minLenI>-1){
return s.substring(minLenI,minLenJ);
}
return "";
} View Code
但是有个问题，如果s很大，t很大。就会超出内存限制。。。
然后我用哈希表存储字符出现的个数，妄图遍历所有组合。不出意外的超时。
public static boolean containsAll(HashMap<Character,Integer> src,HashMap<Character,Integer> subSrc){
for(char c : src.keySet()){
if(subSrc.getOrDefault(c,0)<src.get(c) ) return false;
}
return true;
}
public static int[] shrink(char[] s,String t,int start,int end,HashMap<Character,Integer> src,HashMap<Character,Integer> subSrc){
while (start<end){
if(t.indexOf(s[start])!=-1){
subSrc.put(s[start],subSrc.get(s[start])-1);
if(containsAll(src,subSrc)){
start++;
continue;
}else{
break;
}
}else{
start++;
}
}
return new int[]{start,end+1};
}
public static String minWindow(String s, String t) {
char[] tCharArray = t.toCharArray();
char[] sCharArray = s.toCharArray();
int lenS = s.length();
int lenT = t.length();
if(lenT>lenS) return "";
int dis = Integer.MAX_VALUE;
int ans[] = new int[2];
HashMap<Character,Integer> count = new HashMap<>();
for(int i=0;i<lenT;i++){
count.put(tCharArray[i],count.getOrDefault(tCharArray[i],0)+1);
}
HashMap<Character,Integer> subCount = new HashMap<>();
for(int i=0;i<lenS;i++){
if(lenS-i<lenT) break;
if(t.indexOf(sCharArray[i])!=-1){
subCount.clear();
for(int j=i;j<lenS;j++){
if(t.indexOf(sCharArray[j])!=-1){
subCount.put(sCharArray[j],subCount.getOrDefault(sCharArray[j],0)+1);
if(containsAll(count,subCount)){
int[] tmp = shrink(sCharArray,t,i,j,count,subCount);
if((tmp[1]-tmp[0])<dis){
ans[0]=tmp[0];
ans[1]=tmp[1];
dis=tmp[1]-tmp[0];
}
}
}
}
}
}
if(dis<Integer.MAX_VALUE) return s.substring(ans[0],ans[1]);
return "";
} 看了题解，改成滑动窗口。仍然用哈希表记录字符出现的个数：
public static boolean containsAll(HashMap<Character,Integer> src,HashMap<Character,Integer> subSrc){
for(char c : src.keySet()){
if(subSrc.getOrDefault(c,0)<src.get(c) ) return false;
}
return true;
}
public static int[] shrink(char[] s,String t,int start,int end,HashMap<Character,Integer> src,HashMap<Character,Integer> subSrc){
while (start<end){
if(t.indexOf(s[start])!=-1){
subSrc.put(s[start],subSrc.get(s[start])-1);
if(containsAll(src,subSrc)){
start++;
continue;
}else{
break;
}
}else{
start++;
}
}
return new int[]{start,end+1};
}
public static String minWindow(String s, String t) {
char[] tCharArray = t.toCharArray();
char[] sCharArray = s.toCharArray();
int lenS = s.length();
int lenT = t.length();
if(lenT>lenS) return "";
int dis = Integer.MAX_VALUE;
int ans[] = new int[2];
HashMap<Character,Integer> count = new HashMap<>();
for(int i=0;i<lenT;i++){
count.put(tCharArray[i],count.getOrDefault(tCharArray[i],0)+1);
}
HashMap<Character,Integer> subCount = new HashMap<>();
int start = 0;
int end = start;
while (end<lenS){
while(end<lenS){
if(t.indexOf(sCharArray[end])!=-1){
subCount.put(sCharArray[end],subCount.getOrDefault(sCharArray[end],0)+1);
if(containsAll(count,subCount)) break;
}
end++;
}
while (start<=end&&end<lenS){
if(t.indexOf(sCharArray[start])!=-1){
subCount.put(sCharArray[start],subCount.get(sCharArray[start])-1);
if(!containsAll(count,subCount)){
if(end-start<dis){
dis=end-start;
ans[0]=start;
ans[1]=end+1;
}
start++;
end++;
break;
}
}
start++;
}
}
if(dis<Integer.MAX_VALUE) return s.substring(ans[0],ans[1]);
return ""; 一点都不优雅。继续看题解。发现优雅的解法。
- t中的字符，走不出 ascii码，所以我们可以用一个 128长度的数组记录所有t中的字符，及它出现的次数。
- 用一个整数记录已经匹配到字符数。
这样就可以优雅的滑动窗口了：
public static String minWindow2(String s, String t) {
int lenS = s.length();
int lenT = t.length();
if(lenT==0||lenS<lenT)return "";
char[] sC = s.toCharArray();
char[] tC = t.toCharArray();
int[] record = new int[128];
for(int i=0;i<lenT;i++){
record[tC[i]]++;
}
int left=0,right=0;
int match = 0;
int[] ans = new int[2];
int dis = Integer.MAX_VALUE;
while (right<lenS){
record[sC[right]]--;
if(record[sC[right]]>=0) match++;
right++;
while (match==lenT){
if(dis>right-left){
dis=right-left;
ans[0]=left;
ans[1]=right;
}
record[sC[left]]++;
if(record[sC[left]]>0) match--;
left++;
}
}
return s.substring(ans[0],ans[1]);
} 重点看一下滑动窗口这里：
int left=0,right=0;
int match = 0;
int[] ans = new int[2];
int dis = Integer.MAX_VALUE;
while (right<lenS){
record[sC[right]]--;
if(record[sC[right]]>=0) match++;
right++;
while (match==lenT){
if(dis>right-left){
dis=right-left;
ans[0]=left;
ans[1]=right;
}
record[sC[left]]++;
if(record[sC[left]]>0) match--;
left++;
}
} record记录了t串中有多少个字符没有在窗口中。初始为t串中的所有字符。
当窗口滑动时。我们把right指向的字符从record中减掉一个。这个时候，如果record上的字符个数>=0,说明匹配到一个t中的字符。match++。
当match==lenT的时候，说明从letf到right的窗口中包含了t中所有字符串。此时我们收缩窗口。