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

🚩传送门：力扣题目

题目

给定两个字符串 和 ，找到 中所有 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

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

解题思路：滑动窗口

我们可以在字符串 中构造一个长度为与字符串 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；
当窗口中每种字母的数量与字符串 中每种字母的 数量相同 时，则说明当前窗口为字符串 的异位词。

在算法的实现中，我们可以使用来存储字符串 和滑动窗口中每种字母的数量。

复杂度分析

时间复杂度：，其中 为字符串的长度。

空间复杂度：,其中 为字符串的长度。

官方代码

class Solution {
    public static List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null || s.length() < p.length())
            return new LinkedList<Integer>();
        LinkedList<Integer> res = new LinkedList<>();
        HashMap<Character, Integer> map = new HashMap<>();     // 窗口中字母个数
        HashMap<Character, Integer> pmap = new HashMap<>();    // 模式串字母个数
        // p长度,滑动窗口大小
        int k = p.length();
        // 预先 K 窗口,
        for (int i = 0; i < k; i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            pmap.put(p.charAt(i), pmap.getOrDefault(p.charAt(i), 0) + 1);
        }
        // 开始滑动
        for (int i = p.length(); i < s.length(); i++) {
            // 字母数相同说明匹配
            if (map.equals(pmap)) {
                res.add(i - k);
            }
            // 添加i值
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            // 删除i-k值,先个数减1,若为0则删除
            map.put(s.charAt(i - k), map.getOrDefault(s.charAt(i - k), 1) - 1);
            if (map.get(s.charAt(i - k)) == 0) map.remove(s.charAt(i - k));
        }
        if (map.equals(pmap)) {
            res.add(s.length() - k);
        }
        return res;
    }
}