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

难度：中等

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

解题思路

这里利用了 242 题的判断字母异位词的方法。

我的思路：

设定结果集合 result，初始为空
逐个字符来遍历字符串 s，把 s 中的不同位置为起始，长度和 p 相同的字符串给提取出来，令其为 str
调用 isAnagram(str , p) 方法来判断字符串是否为字母异位词
- 若是字母异位词，则将 str 首字符在 s 中的索引下标加入 result 集合
最后返回 result

我的代码

java

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i <= s.length() - p.length(); i++) {
        String str = s.substring(i, i + p.length());
        if (isAnagram(str, p)) {
            result.add(i);
        }
    }
    return result;
}

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] record = new int[26];
    for (int i = 0; i < s.length(); i++) {
        record[s.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
    }

    for (int i = 0; i < t.length(); i++) {
        if (record[t.charAt(i) - 'a'] > 0) {
            record[t.charAt(i) - 'a']--;
        } else {
            return false;
        }
    }
    return true;
}

更优解法（滑动窗口）

思路概述

这个题有点像 76. 最小覆盖字串 ，那么能不能仿照 76 题，来一点 滑动窗口 的做法呢？

我的思路：

设定结果列表 result 用于记录目标子串的起始位置集合
设定哈希表 tFrequency 用来存储字符串 t 中每个字符的频率，该频率就代表了目标子串中每个字符的数量要求，哈希表 window 用于存储当前窗口内字符的频率
设定变量 required 表示字符串 t 中字符的种类数目，变量 formed 用于跟踪当前窗口中满足 tFrequency 的字符条件的字符数目，初始为 0
目标子串需要满足的条件是 right - left == p.length()，且 required 和 formed 相等
设定指针 left 和 right 表示滑动窗口的左右边界，这个窗口在字符串 s 上移动
随着 right 指针的移动，窗口逐渐扩大，此时：
1. 暂存 right 指向的字符，并将 right 右移
2. 将暂存的字符加入 window，或者更新该字符在 window 中的频率
3. 如果暂存的字符在 tFrequency 中存在，并且在 window 中的计数刚好满足了 tFrequency 中对应的数量要求，则增加 formed 的计数，当前子串有可能是目标字符串中的一部分。
4. 当 right - left 等于 p.length()，说明不管现在是否找到目标子串，窗口都要开始移动了
  1. 当 formed 等于 required（即窗口中已包含所有 t 中的字符，且频率也对应）时，说明已经获得了一个满足要求的目标字串，此时存储 left 进 result 列表
  2. 暂存 left 指向的字符，并将 left 右移来缩小窗口
  3. 如果暂存的字符在 tFrequency 中存在，并且在 window 中的计数满足 tFrequency 中的要求，说明即将移除的字符会影响 formed 的计数，故减少 formed 的计数
  4. 将暂存的字符从 window 中移除
最终，返回 result

代码展示

java

public List<Integer> findAnagrams(String s, String p) {
    // 结果列表
    List<Integer> result = new ArrayList<>();
    // 存储字符串 p 中每个字符的频率
    HashMap<Character, Integer> pFrequency = new HashMap<>();
    for (char c : p.toCharArray()) {
        pFrequency.put(c, pFrequency.getOrDefault(c, 0) + 1);
    }
    // 表示字符串 p 中字符种类的数目
    int required = pFrequency.size();
    // 用合适的数据结构记录窗口中的字符及其频率
    HashMap<Character, Integer> window = new HashMap<>();
    // 跟踪当前窗口中满足 p 的字符条件的字符数量
    int formed = 0;

    // 窗口的左右边界
    int left = 0;
    int right = 0;
    while (right < s.length()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 如果当前字符的计数满足 p 中的要求，更新 formed 计数
        if (pFrequency.containsKey(c) && window.get(c).intValue() == pFrequency.get(c).intValue()) {
            formed++;
        }
        // 当前子串长度已经达到目标的时候，左侧窗口要开始收缩了
        while (right - left == p.length()) {
            // 若找到了一个满足要求的子串，此处更新结果
            if (formed == required) {
                result.add(left);
            }
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            left++;
            // 如果当前字符的计数满足 p 中的要求，更新 formed 计数
            if (pFrequency.containsKey(d) && window.get(d).intValue() == pFrequency.get(d).intValue()) {
                formed--;
            }
            // 进行窗口内数据的一系列更新
            window.put(d, window.get(d) - 1);
        }
    }
    return result;
}

总结

数组就是简单的哈希表，但是数组的大小不是无限开辟的。

滑动窗口统一套路：

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。
在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 right 指针，和一个用于「收缩」窗口的 l 指针。
在任意时刻，只有一个指针运动，而另一个保持静止。
我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

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

解题思路 ​

我的代码 ​

更优解法（滑动窗口） ​

思路概述 ​

代码展示 ​

总结 ​