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

1.题目

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

给定两个字符串 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" 的异位词。

2.思路

由于异位词是单词数量相同，顺序不一定相同，先用两个哈希表将俩个字符串装进去，然后判断两个哈希表是否相同，相同就将起始位置0收集，之后用滑动窗口判断要求，将s的有边界加入到哈希表中，将s的左边界移除哈希表，每次移动完后判断两个哈希表是否相等，相等则记录当前的窗口起始位置

3.代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        unordered_map<char, int> scount, pcount;

        // 初始化p的字符计数
        for (int i = 0; i < p.size(); ++i) {
            pcount[p[i]]++;
        }

        // 初始化s的第一个窗口的字符计数,窗口大小是p的大小
        for (int i = 0; i < p.size(); ++i) {
            scount[s[i]]++;
        }

        // 检查两个初始哈希是否相等
        if (scount == pcount) {
            ret.push_back(0);
        }

        // 开始滑动窗口
        int right = p.size();
        while (right < s.size()) {
            // 新加入窗口的字符
            scount[s[right]]++;

            // 窗口移出的字符
            int left = right - p.size();
            scount[s[left]]--;
            
            // 如果某个字符的计数降为0，则从map中移除该字符
            if (scount[s[left]] == 0) {
                scount.erase(s[left]);
            }

            // 检查当前窗口是否为anagram
            if (scount == pcount) {
                ret.push_back(right - p.size() + 1);
            }

            // 移动窗口
            ++right;
        }

        return ret;
    }
};