面试指南——最小包含子串的长度

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,表示不存在
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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));

    }

}
0 条评论
发表一条评论