leetcode 链接：438. 找到字符串中所有字母异位词

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指字母相同，但排列不同的字符串。
s 和 p 仅包含小写字母。

示例：

  1. 输入: s = "cbaebabacd", p = "abc"
  2. 输出: [0,6]
  3. 解释:
  4. 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
  5. 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解答 & 代码

滑动固定长度的窗口
设置两个哈希表：

  • pChCntMap 存储字符串 p 所有字符及其出现次数
  • winChCntMap 存储窗口内所有字符及其出现次数

每次滑动窗口（窗口长度固定，left 和 right 同时滑动一格），比较两个哈希表存的字符及其出现次数是否相同，如果相同，则将 left 存入结果数组

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sizeS = s.size();
        int sizeP = p.size();
        vector<int> result;

        unordered_map<char, int> pChCntMap;
        for(int i = 0; i < sizeP; ++i)
        {
            if(pChCntMap.find(p[i]) == pChCntMap.end())
                pChCntMap[p[i]] = 1;
            else
                ++pChCntMap[p[i]];
        }

        int left = 0;
        int right = 0;
        unordered_map<char, int> winChCntMap;
        while(right < sizeP - 1)
        {
            if(winChCntMap.find(s[right]) == winChCntMap.end())
                winChCntMap[s[right]] = 1;
            else
                ++winChCntMap[s[right]];
            ++right;
        }

        while(right < sizeS)
        {
            if(winChCntMap.find(s[right]) == winChCntMap.end())
                winChCntMap[s[right]] = 1;
            else
                ++winChCntMap[s[right]];

            bool flag = true;
            for(auto it = winChCntMap.begin(); it != winChCntMap.end() && flag; ++it)
            {
                if(pChCntMap.find(it->first) == pChCntMap.end() || pChCntMap[it->first] != it->second)
                    flag = false;
            }
            if(flag)
                result.push_back(left);

            --winChCntMap[s[left]];
            if(winChCntMap[s[left]] == 0)
                winChCntMap.erase(s[left]);
            ++right;
            ++left;
        }
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：72 ms, 在所有 C++ 提交中击败了 9.88% 的用户
内存消耗：12.5 MB, 在所有 C++ 提交中击败了 7.25% 的用户