【滑动窗口】找到字符串中所有字母异位词

题目

438. 找到字符串中所有字母异位词

剑指 Offer II 015. 字符串中的所有变位词

---

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10^4
• s 和 p 仅包含小写字母

解题

方法一：滑动窗口

思路

与【暴力, 枚举, 滑动窗口】字符串的排列几乎完全一样，只不过从求符合条件的子串是否存在变成了求所有符合条件的子串的集合。

代码

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;
    }
}