LeetCode438. 找到字符串中所有字母异位词（2024秋季每日一题 11）

给定两个字符串 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” 的异位词。

提示:

$1<=s.length,p.length<=3\ast 10^4$
s 和 p 仅包含小写字母

---

思路：

• 维护两个 cnt 数组，pcnt、scnt，pcnt[x] 表示字母 x 出现的次数，x= [‘a’~‘z’]
• 扫描 s 字符串，对每一个长度为 p.size() 的子串，维护一个 scnt 数组
• 当子串的 scnt 每个位置（即每个字母）的数量等于 pcnt 时，则代表 当前子串与 p 串是异位词
• 而对于 c++ 中的 vector，可以直接进行比较，相当于比较数组内对应下标每个元素的大小
• 而当对 s 从前往后扫描长度为 p.size() 的子串的时候，可以维护一个滑动窗口
  • 当子串按顺序往后扫描一个时，就相当于窗口向后挪了一个位置，对于子串的改变，相当于在子串中加了一个字母 s[i]，而去掉了一个字母 s[i-p.size()]，而对当前子串中所有字母数量的的改变也只有 scnt[s[i]] 和 scnt[i-p.size()]

时间复杂度：O(N*M)，M = 26;

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> res;vector<int> pcnt(30, 0), scnt(30, 0);for(int i = 0; i < p.size(); i++){pcnt[p[i] - 'a']++;if(i < s.size()) scnt[s[i] - 'a']++;}if(pcnt == scnt) res.push_back(0);for(int i = p.size(); i < s.size(); i++){scnt[s[i] - 'a']++, scnt[s[i - p.size()]-'a']--;if(pcnt == scnt) res.push_back(i - p.size() + 1);}return res;}
};