面试算法15：字符串中的所有变位词

题目

输入字符串s1和s2，如何找出字符串s2的所有变位词在字符串s1中的起始下标？假设两个字符串中只包含英文小写字母。例如，字符串s1为"cbadabacg"，字符串s2为"abc"，字符串s2的两个变位词"cba"和"bac"是字符串s1中的子字符串，输出它们在字符串s1中的起始下标0和5。

分析

如果字符串s2的长度为n，则逐个统计字符串s1中所有长度为n的子字符串中字母出现的次数。可以用两个指针来定位字符串s1的子字符串，第1个指针指向字符串的第1个字符，第2个指针指向字符串的最后一个字符。每次统计完子字符串中字符出现的次数之后，两个指针同时向右移动一位。两个指针每向右移动一位，相当于在上一次的子字符串的最右边加上一个字母，并删除原来子字符串最左边的字母。
每当在子字符串中添加一个字母，则把哈希表中该字母对应的值减1；每当从子字符串中删除一个字母，则把哈希表中该字母对应的值加1。如果哈希表中所有的值都是0，那么由两个指针定位的子字符串是字符串s2的一个变位词。按照题目要求，把第1个指针对应的下标添加到结果链表中。

分析

public class Test {
    public static void main(String[] args) {
        List<Integer> result = findAnagrams("cbadabacg", "abc");
        System.out.println(result);
    }

    public static List<Integer> findAnagrams(String s1, String s2) {
        List<Integer> indices = new LinkedList<>();
        if (s1.length() < s2.length()) {
            return indices;
        }

        int[] counts = new int[26];
        int i = 0;
        for (; i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']++;
            counts[s1.charAt(i) - 'a']--;
        }

        if (areAllZero(counts)) {
            indices.add(0);
        }

        for (; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']--;
            // 曾经减减过，现在已经不包含那个字符了，要确保对count[]没有影响，所以需要加加
            counts[s1.charAt(i - s2.length()) - 'a']++;
            if (areAllZero(counts)) {
                indices.add(i - s2.length() + 1);
            }
        }

        return indices;
    }

    private static boolean areAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}
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
42
43
44
45