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

题目

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例

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

思路

这是一道经典的字符串匹配问题，可以使用滑动窗口算法来解决。

具体思路如下：

1. 首先，我们需要统计模式串 p 中每个字符出现的次数，并保存到一个数组中。然后，我们可以枚举 s 中长度为 m 的子串（m 为模式串的长度），并统计每个子串中字符出现的次数。

2. 对于每个子串，我们可以通过比较其字符频次数组和模式串的字符频次数组，来判断它是否为 p 的异位词。如果是，则将其起始索引加入到结果数组中。

3. 由于 s 和 p 只包含小写字母，因此我们可以使用一个长度为 26 的数组来保存字符频次，这样可以在 O(1) 时间内统计字符出现的次数。

4. 采用滑动窗口算法，首先将 s 的前 m 个字符作为初始窗口，然后每次向右移动一个字符，更新窗口内字符频次数组，然后判断窗口内子串是否为 p 的异位词。

5. 最后，返回所有符合条件的子串的起始索引。

Code

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.length();
        int m = p.length();
        if (n < m) {
            return vector<int>();
        }
        vector<int> ans;
        vector<int> svis(26);
        vector<int> pvis(26);
        for (int i = 0; i < m; i++) {
            ++svis[s[i] - 'a'];
            ++pvis[p[i] - 'a'];
        }

        if (svis == pvis) {
            ans.emplace_back(0);
        }

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

            if(svis == pvis){
                ans.emplace_back(i+1);
            }
        }

        return ans;
    }
};
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