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

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

给定两个字符串 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 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

使用滑动窗口来实现。使用两个哈希表记录滑动窗口以及字符串p中的字符的数量，不断移动窗口的右端，将字符串s中的字符加入到滑动窗口中。如果加入的字符不在字符串p中，则直接跳到下个字符；否则将字符加入到滑动窗口中，如果字符数目超了，不断将左侧字符出窗口直到字符数目不超；最后如果滑动窗口的字符数目符合p的数目，则找到一个答案，左侧出窗口。

code

class Solution {
public:
    //滑动窗口
    //记录滑动窗口内的字母数目
    //满足则出和入
    //不是p的字符，跳到下一个
    //数目超了移动到数目符合为止

    vector<int> findAnagrams(string s, string p) {
        
        vector<int> ans;

        unordered_map<char,int> cnts,cntp;

        for(auto c : p) cntp[c] ++;

        int l = 0,r = 0;

        while(r < s.size())
        {

            
            //当前加入的字符不存在p中
            if(cntp.find(s[r]) == cntp.end()) 
            {
                l = r + 1;
                r = r + 1;
                cnts.clear();
                continue;
            }
            else
            {
                
                cnts[s[r]] ++;
                
                //字符数目多，不断移动左指针将字符移出窗口
                while(cnts[s[r]] > cntp[s[r]])
                {
                    
                    cnts[s[l]] --;
                    l ++;
                }
            }

            //如果加入的字符s[r]符合长度则找到一个
            if(r - l + 1 == p.size())
            {
                ans.push_back(l);
                cnts[s[l]] --;
                l ++;
                r ++;
            }
            else
            {
                r ++;
            }
        }

        return ans;
    }
};