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

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

题目描述

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

示例

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

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

解析

双指针 + 滑动窗口：

• 维护两个窗口，一个是所需p字符和数量的哈希表窗口，另一个是判断异位词的窗口
• 当字符串中的字符满足 need 窗口时，入窗口添加到 window中，判断二者字符和数量是否相等
• 当 window 中字符数量大于 p 字符长度时进行出窗口操作，判断是否满足结果，在进行出窗口操作

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for (char ch : p.toCharArray()) {
            need.put(ch, need.getOrDefault(ch, 0) + 1);
        }

        int left = 0, right = 0, valid = 0;
        List<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            char in = s.charAt(right++);
            if (need.containsKey(in)) {
                window.put(in, window.getOrDefault(in, 0) + 1);
                if (need.get(in).equals(window.get(in))) {
                    valid++;
                }
            }

            while (right - left >= p.length()) {
                if (need.size() == valid) {
                    res.add(left);
                }
                char out = s.charAt(left++);
                if (need.containsKey(out)) {
                    if (need.get(out).equals(window.get(out))) {
                        valid--;
                    }
                    window.put(out, window.get(out) - 1);
                }
            }
        }

        return res;
    }
}