【滑动窗口】字符串的排列

题目

567. 字符串的排列

剑指 Offer II 014. 字符串中的变位词

---

给你两个字符串 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 仅包含小写字母

解题

方法一：暴力 枚举

思路

暴力枚举 s2 中所有长度为 s1.length() 的子字符串并判断其与 s2 的字符组成是否相同。

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] targetCnts = new int[26];
        for (char ch : s1.toCharArray()) ++targetCnts[ch - 'a']; 
        char[] chs = s2.toCharArray();
        int n1 = s1.length(), n2 = chs.length;
        int[] cnts = new int[26];
        outer: for (int i = 0; i <= n2 - n1; ++i) {
            Arrays.fill(cnts, 0);
            for (int j = i; j < i + n1; ++j) {
                int idx = chs[j] - 'a';
                if (++cnts[idx] > targetCnts[idx]) continue outer;
            }
            return true;
        }
        return false;
    }
}

方法二：滑动窗口

思路

与【哈希表, 滑动窗口】最小覆盖子串的滑窗有异曲同工之妙，只不过窗口几乎变成了固定长度，所以在左指针增加时不用循环，只需要判断窗口大小是否等于 s1 的长度就行了。

代码

class Solution {
    static final int HASH_LEN = 'z' + 1;

    public boolean checkInclusion(String s1, String s2) {
        int[] require = new int[HASH_LEN], window = new int[HASH_LEN];
        int target = 0;
        for (char ch : s1.toCharArray()) {
            if (++require[ch] == 1) ++target;
        }
        char[] chs = s2.toCharArray();
        int m = s1.length(), n = chs.length;
        int left = 0, right = 0, valid = 0;
        while (right < n) {
            int idx = chs[right++];
            if (++window[idx] == require[idx]) ++valid;
            if (right - left >= m) {
                if (valid == target) return true;
                idx = chs[left++];
                if (window[idx]-- == require[idx]) --valid;
            }
        }
        return false;
    }
}