📝 题目描述

题目链接：找到字符串中所有字母异位词

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

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

示例 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 仅包含小写字母

💡 解题思路

方法一：滑动窗口

首先来想一个最朴素的解法：
确定字符串 p 的长度 n，字符串 s 的长度 m。然后对于字符串 s，从 s[0] 开始，一直到 s[m - n]，不断尝试以 s[i] 为起点， s[i + n - 1] 为终点的子串是否是字符串 p 字母异位词（排序后比较），若是则标记 s[i] 的位置进入答案。
上面这种方法虽然容易想到，但时间复杂度过高，达到了 O(N⋅MlogM)O(N⋅MlogM) ，会出现超时。

接下来我们可以思考一下时间花在了哪，最耗时的是排序的一步，我们需要在每一次循环中对字符串进行排序，那有没有方法可以绕过排序来进行是否为字母异位词的判断呢？

由于题目中说了字符串组成成分仅含小写字母，因此我们可以维护一个 vector<int> mCount(26) ，代表子串中26个英文字母的数量情况，并设置字符串 p 的字母分布情况为 vector<int> nCount(26) ，当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词，这样就做到了通过对比两个数组来降低时间复杂度。

方法二：优化的滑动窗口

明白了上面的道理，我们可以进一步优化滑动窗口，我们可以不再分别统计滑动窗口和字符串 p 中每种字母的数量，而是统计滑动窗口和字符串 p 中每种字母数量的差；并引入变量 differ 来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它。

在判断滑动窗口中每种字母的数量与字符串 p 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。

🔧 代码实现

1、滑动窗口

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        vector<int> ans;
        // 很重要，s.size() 和 p.size() 返回的类型是 size_t，它是无符号的，相减会溢出
        if (m < n) return ans;
        vector<int> mCount(26, 0);
        vector<int> nCount(26, 0);

        for(int i = 0; i < n; i++){
            mCount[s[i] - 'a']++;
            nCount[p[i] - 'a']++;
        }

        if (mCount == nCount) ans.push_back(0);

        for(int i = n; i < m; i++){
            mCount[s[i] - 'a']++;
            mCount[s[i - n] - 'a']--;
            if(mCount == nCount) ans.push_back(i - n + 1);
        }
        return ans;
    }
};

2、优化的滑动窗口

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size(), differ = 0;
        vector<int> ans;
        if (m < n) return ans;
        vector<int> mCount(26, 0);
        for(int i = 0; i < n; i++){
            mCount[s[i] - 'a']++;
            mCount[p[i] - 'a']--;
        }

        for(int i = 0; i < 26; i++){
            if(mCount[i] != 0) differ++;
        }

        if(differ == 0) ans.push_back(0);

        for(int i = n; i < m; i++){
            // mCount[s[i] - 'a']++;
            // mCount[s[i - n] - 'a']--;

            // differ = 0;
            // for(int j = 0; j < 26; j++){
            //     if(mCount[j] != 0) differ++;
            // }

            if (mCount[s[i - n] - 'a'] == 1){
                differ--;
            } else if (mCount[s[i - n] - 'a'] == 0){
                differ++;
            }
            mCount[s[i - n] - 'a']--;

            if (mCount[s[i] - 'a'] == -1){
                differ--;
            } else if (mCount[s[i] - 'a'] == 0){
                differ++;
            }
            mCount[s[i] - 'a']++;

            if(differ == 0) ans.push_back(i - n + 1);
        }
        return ans;
    }
};

📊 复杂度分析

1、滑动窗口

  • 时间复杂度：O(n+(m−n)×Σ)O(n+(m−n)×Σ)，其中 mm 为字符串 s 的长度，nn 为字符串 p 的长度，ΣΣ 为所有可能的字符数。我们需要 O(n)O(n) 来统计字符串 p 中每种字母的数量；需要 O(n)O(n) 来初始化滑动窗口；需要判断 m−n+1m − n + 1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ)O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26Σ=26。
  • 空间复杂度：O(Σ)O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。

2、优化的滑动窗口

  • 时间复杂度：O(m+n+Σ)，其中 mm 为字符串 s 的长度，nn 为字符串 p 的长度，其中 ΣΣ 为所有可能的字符数。我们需要 O(n)O(n) 来统计字符串 p 中每种字母的数量；需要 O(n)O(n) 来初始化滑动窗口；需要 O(Σ)O(Σ) 来初始化 differ；需要 O(m−n)O(m−n) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(1)O(1) 。因为 s 和 p 仅包含小写字母，所以 Σ=26Σ=26。
  • 空间复杂度：O(Σ)O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差。

🎯 总结

  • 核心思想：如何由朴素的暴力解法想到使用数组存储字母分布情况。