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

题目

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

示例

示例 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" 的字母异位词。

方法（滑动窗口）

因为s和p中全部都是小写字符，因此我们可以分别用大小为26的桶来记录字符串中出现的字符及其出现的次数

• 先将p中的字符全部入桶bucketP。
• 用left和right分别记录s中滑动窗口的左右端点，准备一个桶bucketS记录此滑动窗口中的字符及其出现次数
• right不断向右移动，每移动一次都将一个新的字符加入到桶bucketS中。
• 当桶bucketS中元素种类或个数比桶bucketP多时，此时right再向右只会让二者差的更多，不可能找到字母异位词。因此这时应该将滑动窗口的左端向右移动，将一些字符踢出桶，直到桶bucketS和桶bucketP中元素相同为止。
• 当桶bucketS中元素种类或个数与桶bucketP完全相同时，只需要判断窗口的长度和p是否相同，就可判断是否找到字母异位词

代码

public List<Integer> findAnagrams(String s, String p) {
    //corner case
    List<Integer> res = new LinkedList<>();
    if(s == null || s.length() < p.length())
        return res;
    int[] bucketP = new int[26];
    for(int i = 0; i < p.length(); i++)
        bucketP[p.charAt(i) - 'a']++;
    int[] bucketS = new int[26];
    //left和right分别为滑动窗口的左右端点
    int left = 0;
    int right = 0;
    while(right < s.length()){
        int curR = s.charAt(right) - 'a';
        bucketS[curR]++;
        right++;
        while(bucketS[curR] > bucketP[curR]){
            int curL = s.charAt(left) - 'a';
            bucketS[curL]--;
            left++;
        }
        if(right - left == p.length())
            res.add(left);
    }
    return res;
}