leetcode

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

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

超时代码

用滑动窗口去遍历整个字符串，每次遍历到一个字串就sort一次，再与sort好的字符串 p 比较，当字符串长度过长时，这个做法肯定会超时.

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;int len_s = s.length(); // s的长度int len_p = p.length(); // p的长度sort(p.begin(), p.end()); // 对p进行排序int i = 0, j = i + len_p - 1; // 滑动窗口while (j < len_s) {// 将滑动窗口中的字串取出，存放到tmp中string tmp = "";tmp.append(s.substr(i, len_p));sort(tmp.begin(), tmp.end());if (!tmp.compare(p)) { // 若两个字符串相等ans.push_back(i);}i++, j++; // 往后移动滑动窗口}return ans;}
};

正确做法

同样的滑动窗口思路，但是判断字符串是否是字母异位词，改用长度为26的数组来记录遍历到的字串中字母出现的次数与 p 字符串中字母出现的次数，若两者相同，则是字母异位词。代码如下

class Solution {
public:vector<int> findAnagrams(string s, string p) {int len_s = s.length(); // s的长度int len_p = p.length(); // p的长度if (len_s < len_p) return vector<int>();vector<int> ans;vector<int> sCNT(26); // 记录s串中字母出现次数vector<int> pCNT(26); // 记录p串中字母出现次数for (int i = 0; i < len_p; ++i) {++sCNT[s[i] - 'a'];++pCNT[p[i] - 'a'];}// 0位置开始的滑动窗口中的字符串与目标字符串互为字母异位if (sCNT == pCNT) ans.push_back(0); for (int i = 0; i < len_s - len_p; ++i) {// 移动窗口--sCNT[s[i] - 'a'];++sCNT[s[i + len_p] - 'a'];if (sCNT == pCNT) {ans.push_back(i + 1);}}return ans;}
};