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