- 給定字符串str1和str2赞季，求str1的子串中含有str2所有字符的最小子串長度
【舉例】
str1="abcde"敛摘，str2="ac"
因為"abc"包含 str2 所有的字符，并且在滿足這一條件的str1的所有子串中雄右，"abc"是 最短的厕怜，返回3。
str1="12345"未檩，str2="344" 最小包含子串不存在戴尸，返回0。
/**
* 給定字符串str1和str2冤狡，求str1的子串中含有str2所有字符的最小子串長度
* 【舉例】
* str1="abcde"孙蒙，str2="ac"
* 因為"abc"包含 str2 所有的字符，并且在滿足這一條件的str1的所有子串中悲雳，"abc"是 最短的挎峦，返回3。
* str1="12345"怜奖，str2="344" 最小包含子串不存在浑测，返回0翅阵。
*/
public class MinSubStrLen {
// 建立詞頻表歪玲，和統(tǒng)計str2字符總數(shù)all
// 遍歷str1每到一個位置讓相應詞頻表--,all--
// 當all小于0時移動L，
public static int minSubStrLen(String str1,String str2){
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
// 字符從0~255,比如'a'字符的個數(shù)用map[a] = 1
int[] map = new int[256];
for(int i = 0;i < c2.length;i++){
map[c2[i]] += 1;
}
int all = str2.length();
int left = 0;
int right = 0;
int min = Integer.MAX_VALUE;
while (right < str1.length()){
map[c1[right]]--;
if(map[c1[right]] >= 0){
all--;
}
if(all == 0){
// 已經(jīng)把str2遍歷完了,縮小left,left往右移動的過程中只要保持all = 0,那么就是符合題意的子串
// 當left移動到使all > 0 的時候收集第一當前最小的答案
while (map[c1[left]] < 0){
map[c1[left++]] ++;
// 此時all用增加left向右繼續(xù)移動
}
// 當移動到一個位置掷匠，使得詞頻表中的某個字符大于0
min = Math.min(min,right-left+1);
all++;
map[c1[left++]]++;
}
right ++;
}
return min == Integer.MAX_VALUE ? 0 : min;
}
public static void main(String[] args) {
String str1 = "abcde";
String str2 = "ac";
System.out.println(minSubStrLen(str1, str2));
}
}
