438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1: Input: s: “cbaebabacd” p: “abc”

Output: [0, 6]

Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, which is an anagram of “abc”.Example 2: Input: s: “abab” p: “ab”

Output: [0, 1, 2]

Explanation: The substring with start index = 0 is “ab”, which is an anagram of “ab”. The substring with start index = 1 is “ba”, which is an anagram of “ab”. The substring with start index = 2 is “ab”, which is an anagram of “ab”. Runtime: 40 ms, faster than 100.00% of C++ online submissions for Find All Anagrams in a String.
Memory Usage: 7.1 MB, less than 0.89% of C++ online submissions for Find All Anagrams in a String.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> pv(26,0);
        vector<int> sv(26,0);
        vector<int> result;
        if (s.size() < p.size()) {
            return result;
        }
        for(int i = 0; i < p.size(); ++i)
        {
            ++pv[p[i] - 'a'];
            ++sv[s[i] - 'a'];
        }
        if (pv == sv) {
            result.push_back(0);
        }
        for(int i = p.size(); i < s.size(); ++i)
        {
            // sv like a stack
            ++sv[s[i] - 'a'];
            --sv[s[i - p.size()] - 'a'];
            if (pv == sv) {
                result.push_back(i-p.size() + 1);
            }
        }
        return result;
    }
};

解题思路的流程还是比较清晰的，就是依次对子串跟需要对比的字符串进行异构的判断。
异构字符串的判断，只需要统计每个字母的数量，如果两个字符串包含的所有字母及个数都相等，则这两个字符串为异构的字符串。

• 由于被判断字符串 p 是不变的，因此统计的结果可以可缓存的
• 由于每一次判断子串，都只是首尾下标的变化，因此可以把统计的数组当做栈来使用，可以节省空间和时间复杂度