Leetcode热题100_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” 的异位词。

滑动窗口

滑动窗口大小固定，检查固定窗口内字符串是否与p的字符频率相同，如果相同则记录窗口的起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) return new ArrayList<Integer>();

        List<Integer> res = new ArrayList<>();
        int[] pCount = new int[26];
        // 将p中字符的频率存储在count数组中
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        int[] sCount = new int[26];
        for (int right = 0; right < s.length(); right++) {
            // 当前字符进入窗口，记录对应字符的频率
            sCount[s.charAt(right) - 'a']++;

            int left = right - p.length() + 1; // 窗口的左边界
            // 当窗口大小小于p时继续移动
            if (left < 0) continue;

            // 如果当前窗口内的字符频率与p相同，则记录起始索引
            if (Arrays.equals(sCount, pCount)) {
                res.add(left);
            }
            // 当前字符离开窗口，更新对应字符的频率
            sCount[s.charAt(left) - 'a']--;
        }
        return res;
    }
}
  • 时间复杂度：O(∣Σ∣m+n)，其中 m 是 s 的长度，n 是 p 的长度，∣Σ∣=26 是字符集合的大小。
  • 空间复杂度：O(∣Σ∣)。返回值不计入。