str1 和 str2 求str1 的子串 中含有str2 的所有字符的最小字串长度

例如:

str1 ="abcde"

str2="ac"

返回3

/*
* 最小包含子串
* 1.字符串a,b长度检查并转换成字符数组,同时新建一个长度256的int数组
* 2.遍历b数组,b数组每个元素对应的ascii码所对应的int数组++,例如acb遍历完后abc的ascii所对应的下标的位置值为1;
* 3.初始化left=0,right=0,match=b.length,表示:左右目前都是0,match为字符串a目前欠字符串b多少字符,
* 初始化minlen为Integer最小值,表示最小包含子串的长度。
* 4.通过right变量开始从左到右遍历,如果字符串a的字符对应的value减1,减完之后如果等于0,说明减之前大于0,说明a归还了一个b的字符,
* 所以match减1,如果减完之后小于0,match不变;
* 5.在遍历的过程中,如果match等于0,说明从左到右已经归还完毕,开始移动left,如果left当前对应的字符的值小于0,说明如果a拿回这个字符
* 也不欠b,所以当前字符所对应的数组值++,left右移;同时minlen=Math.min(minLen, right - left + 1);
* 6.5步骤操作完后,当前最小子串为(left,right),如果后面有更小的窗口,则从left+1位置开始,所以,当left前面的值小于0,匹配完毕之后,
* 令match++,left下一个元素所对应的值++,继续开始right的移动。
* 7.如果遍历完成后minlen没有发生变化,则返回0,表示不存在
*/
public class 最小包含子串的长度 { public static int minLength(String str1, String str2) { if (str1 == null || str2 == null || str1.length() < str2.length()) { return 0; } char[] chas1 = str1.toCharArray(); char[] chas2 = str2.toCharArray(); int[] map = new int[256]; for (int i = 0; i != chas2.length; i++) { map[chas2[i]]++; } int left = 0; int right = 0; int match = chas2.length; int minLen = Integer.MAX_VALUE; while (right != chas1.length) { map[chas1[right]]--; if (map[chas1[right]] >= 0) { match--; } if (match == 0) { while (map[chas1[left]] < 0) { map[chas1[left++]]++; } minLen = Math.min(minLen, right - left + 1); match++; map[chas1[left++]]++; } right++; } return minLen == Integer.MAX_VALUE ? 0 : minLen; } public static void main(String[] args) { String str1 = "adabbca"; String str2 = "acb"; System.out.println(minLength(str1, str2)); } }