567. 字符串的排列

题目

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

示例 2：

输入：s1= “ab” s2 = “eidboaoo”
输出：false

提示：

1 <= s1.length, s2.length <= 10^4
s1 和 s2 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

看提交记录，发现前前后后复习了很多次，也算是这次可以比较快地写出比较优雅的写法。

因为s2中的子串和s1一定等长，所以滑窗大小是固定的，这其实简化了题目的难度（升级一下就是76题）。

因此，比较直接的思路是使用和s1等长的窗口，统计窗口内字符个数和s1是否相同。比较优雅的写法是只使用一个数组，一开始遍历s1的字符将对应位置数值减1，遍历s2时再将对应数值加1，如果cnt的元素为0，就说明该字符在两个字符串中的数量相同。同时，使用一个变量diff维护数组中0的个数，当diff为0时，说明两个字符串的字符种类及个数完全一致。

代码

滑窗

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] cnt = new int[26];
        int n = s1.length();
        int m = s2.length();
        // 这里特判是必须的，不然下面循环会越界
        if (m < n) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            // 对于s1的字符，将cnt对应位置--
            cnt[s1.charAt(i) - 'a']--;
            // 对于s2的字符，将cnt对应位置++
            cnt[s2.charAt(i) - 'a']++;
        }
        // 两个串中个数不同的字符数
        int diff = 0;
        for (int c : cnt) {
            if (c != 0) {
                diff++;
            }
        }
        // 这句也是必须的，有可能一开始的滑窗就匹配了
        if (diff == 0) {
            return true;
        }
        for (int i = n; i < m; i++) {
            int x = s2.charAt(i) - 'a';
            int y = s2.charAt(i - n) - 'a';
            if (cnt[x] == 0) {
                diff++;
            }
            cnt[x]++;
            if (cnt[x] == 0) {
                diff--;
            }
            if (cnt[y] == 0) {
                diff++;
            }
            cnt[y]--;
            if (cnt[y] == 0) {
                diff--;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
}