字符串中的变位词

? ? ? ? 变位词是字符串相关面试题经常会出的一个概念，它是指组成各个单词的字母及每个字母出现的次数完全相同，只是字母排列的顺序不同。例如，“pots"、"stop"和"tops"就是一组变位词。
? ? ? ? 变位词有以下几个特点。一组变位词的长度一定相同；组成变位词的字母集合一定相同，并且出现的次数也相同。

? ? ? ? 暴力法可以解决，先求出s_1的所有排列，然后判断每个排列是不是字符串s_2的子字符串。假设一个字符串长度为n，那么它一共有n!个排列，因此这个方法时间复杂度不会低于O(n!)。

? ? ? ? 下面介绍一种高效的算法，根据变位词特点的第二条，我们可以很容易想到利用哈希表来统计字符串中每个字母出现的次数。又因为题目要求的字符串只包含小写字母，其个数确定，所以可以用一个数组来模拟哈希表，数组下标依次与字母对应。

? ? ? ? 可以利用双指针思想，在s_2中设置一个固定长度的窗体，长度比s_1的长度大1。首先，先扫描字符串s_1，每扫到一个字符，对应的值加1，同时，扫描第二个字符串s_2中对应位置字符，对应的值减1，然后先做一次判断，如果满足变位词，数组中的所有值应均为0。若不满足再去维护这个滑动窗口。第一个指针为i-s1.length()，第二个指针为i（两指针之间包含s1.length()+1个字符），两个指针都右移1位，每当增加一个字符时，数组对应位置的值减1，每当删除一个字符时，数组对应位置的值加1，每次更新后都去判断数组中的所有值。

    public boolean checkIncumsion(String s1, String s2) {
        // s2的长度小于s1的长度不可能存在包含关系
        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-s1.length()，第二个指针为i
        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 boolean areAllZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

当然还有另一种比较好懂的写法，这里就不再赘述了，道理都一样。

    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; i++) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; i++) {
            cnt2[s2.charAt(i) - 'a']++;
            cnt2[s2.charAt(i - n) - 'a']--;
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }