面试算法14：字符串中的变位词

题目

输入字符串s1和s2，如何判断字符串s2中是否包含字符串s1的某个变位词？如果字符串s2中包含字符串s1的某个变位词，则字符串s1至少有一个变位词是字符串s2的子字符串。假设两个字符串中只包含英文小写字母。例如，字符串s1为"ac"，字符串s2为"dgcaf"，由于字符串s2中包含字符串s1的变位词"ca"，因此输出为true。如果字符串s1为"ab"，字符串s2为"dgcaf"，则输出为false。

分析

由变位词的定义可知，变位词具有以下几个特点。首先，一组变位词的长度一定相同；其次，组成变位词的字母集合一定相同，并且每个字母出现的次数也相同。

由于这个题目强调字符串中只包含英文小写字母，而英文小写字母的个数是确定的，一共26个，因此可以用数组模拟一个简单的哈希表。数组的下标0对应字母’a’，它的值对应字母’a’出现的次数。数组的下标1对应字母’b’，它的值对应字母’b’出现的次数。以此类推，数组的下标25对应字母’z’，它的值对应字母’z’出现的次数。

首先扫描字符串s1。每扫描到一个字符，就找到它在哈希表中的位置，并把它对应的值加1。如果字符串s1为"ac"，那么在该哈希表中，只有字母’a’和字母’c’对应的值是1，其他值都是0，这是因为只有这两个字母在字符串中各出现了1次。
遍历s2所有和s1相同长度的连续子字符串，逐个扫描这个变位词中的字母，并把字母在哈希表中对应的值减1。由于字符串s1的变位词和字符串s1包含相同的字母，并且每个字母出现的次数也相同，因此扫描完字符串s1的变位词之后，哈希表中所有的值都是0。

解

public class Test {
    public static void main(String[] args) {
        boolean result = checkInclusion("ac", "dgcaf");
        System.out.println(result);
    }

    public static boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) {
            return false;
        }

        int[] counts = new int[26];
        // 注意：同位词必须长度相等，不能其中一个词多字母，那不能算同位词
        for (int i = 0; i < s1.length(); i++) {
        	// 曾经减减过，现在已经不包含那个字符了，所以需要加加
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }

        if (areAllZero(counts)) {
            return true;
        }

        // 注意：同位词必须长度相等，不能其中一个词多字母，那不能算同位词
        // i相当于第2个指针，指向子字符串的最后一个字符。第1个指针指向下标为i-s1.length()的位置。两个指针之间的子字符串的长度一直是字符串s1的长度。
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (areAllZero(counts)) {
                return true;
            }
        }

        return false;
    }

    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
46