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

题目

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

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

示例

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

思路

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

具体思路如下：

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

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

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

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

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

Code

class Solution {public:    vector findAnagrams(string s, string p) {        int n = s.length();        int m = p.length();        if (n