每日一练：找到字符串中所有字母异位词

一、题目要求

给定两个字符串 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 * 104
• s 和 p 仅包含小写字母

二、解法1-框取比较 O(N) 效率低

用一个 vector<int> v保存p子串的字符种类（下标）和对应数量（值），以 s 中每一个字符为起点，保存size（p的字符数）个字符，最后比较tmp 与 v 是否相等，相等就纳入返回值中。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int size = p.size();vector<int> v(26,0);for (const auto e : p) {v[e-'a']++;}for (int i = 0; i + size <= s.size(); i++) {vector<int> tmp(26,0);int j = 0;for (; j < size; j++) {if (v[s[i+j]-'a'] == 0) // 优化{i = i + j;break;}tmp[s[i + j]-'a']++;}if (j == size)if (v == tmp) {ret.push_back(i);}}return ret;}
};

         

三、解法2-滑动窗口 O(N)

维护一个滑动窗口，窗口初始化后先进行一次比较，之后窗口每次向后滑动一位，比较一次。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;vector<int> slid_window(26,0); // 滑动窗口vector<int> standard(26,0);    // 比较标准if(s.size() < p.size())return ret;for(int i = 0;i < p.size();i++) // 初始化比较标准和滑动窗口{standard[p[i]-'a']++;slid_window[s[i]-'a']++;}if(standard == slid_window)   // 先进行一次比较{ret.push_back(0);}for(int i = 0;i+p.size() < s.size();i++){// 窗口后移1位slid_window[s[i]-'a']--; // 去掉窗口第一个元素slid_window[s[i+p.size()]-'a']++; // 得到下一个元素if(standard == slid_window) // 比较是否相同{ret.push_back(i+1);}}return ret;}
};

优化：

在解法2的基础上用一个 记录器 count 记录滑动窗口中的字符的数量与种类和目标子串的关系：

每有一个字符的数量或者不同，对应下标的值就不是0，differ就+1。

我们可以用以下逻辑实现：

（1）将 p 中的所有字符记录在 count 中，每有一个字符就自减1

（2）初始化滑动窗口中的字符，每有一个字符就自增1

（3）初始化目前的differ

（4）窗口向后滑动，失去的字符就自减，得到的字符串自加，如果使记录器中的0减少或者增多就更新differ

（5）每次滑动后就判断 differ ，等于0就往答案插入滑动窗口目前的起始下标

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;if (s.size() < p.size())return ret;int differ = 0;                    // 记录不同的字符种类数目vector<int> count(26, 0);          // 记录器for (int i = 0; i < p.size(); i++) // 初始化计数器{count[p[i] - 'a']--;count[s[i] - 'a']++;}for (int i = 0; i < count.size(); i++) { // 初始化differif (count[i] != 0)differ++;}if (differ == 0) // 先进行一次判断{ret.push_back(0);}for (int i = 0; i + p.size() < s.size(); i++) {// 窗口后移1位if (count[s[i] - 'a'] == 1) // 不同变相同differ--;else if (count[s[i] - 'a'] == 0) // 相同变不同differ++;count[s[i] - 'a']--;if (count[s[i + p.size()] - 'a'] == -1) // 不同变相同differ--;else if (count[s[i + p.size()] - 'a'] == 0) // 相同变不同differ++;count[s[i + p.size()] - 'a']++;if (differ == 0) // 比较是否相同{ret.push_back(i + 1);}}return ret;}
};