题目链接

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例

示例1：

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

提示

  • 1 <= s.length, p.length <= 3 * 10

  • s 和 p 仅包含小写字母

    思路

    滑动窗口

    使用数组 freq 记录字符出现的次数（也可以使用哈希表），初始化为 p 中字符出现的频次。为了方便判断，设置变量 count 表示窗口中符合要求的字符个数，初始化为 p 中字符的数量。
    起初，right 指针扩展窗口，将 right 访问过的字符对应频次减一，如果该字符符合条件，count-- ；
    left 指针收缩窗口，将 right 访问过的字符对应频次加一，如果该字符符合条件，count++ ；
    当 count == 0 时， right - left == p.size() 一定是成立的，窗口内的字符串符合条件；
    当 right - left == p.size() 时，若 count 不为 0 ，则要收缩窗口。

    题解

    1. class Solution {
    2.  public:
    3.   vector<int> findAnagrams(string s, string p) {
    4.       vector<int> ans;
    5.       if (s.size() < p.size()) {
    6.           return ans;
    7.       }
    9.       int freq[26] = {0};
    10.       int left = 0, right = 0;
    11.       int count = p.size();
    12.       for (char c : p) {
    13.           freq[c - 'a']++;
    14.       }
    16.       while (right < s.size()) {
    17.           if (freq[s[right] - 'a'] > 0) {
    18.               count--;
    19.           }
    20.           freq[s[right] - 'a']--;
    21.           right++;
    22.           if (0 == count) {
    23.               ans.emplace_back(left);
    24.           }
    25.           if (right - left == p.size()) {
    26.               freq[s[left] - 'a']++;
    27.               if (freq[s[left] - 'a'] > 0) {
    28.                   count++;
    29.               }
    30.               left++;
    31.           }
    32.       }
    34.       return ans;
    35.   }
    36. };

    复杂度分析

  • 时间复杂度：0438-找到字符串中所有字母异位词 - 图1

  • 空间复杂度：0438-找到字符串中所有字母异位词 - 图2，0438-找到字符串中所有字母异位词 - 图3 为字符集大小，这里是26。