438. Find All Anagrams in a String -M

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".

A:

就是两个pointer 一边跑一边看， 数其是否找到足够的anagram。  同时，数其是否找到足够char数目的match

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int nP = p.length(), nS = s.length();
        if(nS < nP)
            return res;
        unordered_map<char,int> pM;
        for(auto ch : p)
            pM[ch]++;
        int pCharCount = pM.size();
        
        unordered_map<char,int> pFound;        
        int matchedChar = 0;
        
        int left =0, right = 0;
        while(left + nP <= nS)
        {
            // run till right pointer till nP length on string s
            for(; right<left+nP; right++)
            {
                char ch = s[right];
                if(pM.find(ch) == pM.end())
                {// not found
                    pFound.clear();
                    matchedChar=0;
                    left = right+1;
                    right++ ;
                    break;
                }else{
                    if(pFound[ch] == pM[ch])
                    {
                        matchedChar--;
                    }
                    pFound[ch]++;
                    if(pFound[ch] == pM[ch])
                    {
                        matchedChar++;
                    }
                    if(matchedChar == pCharCount)
                    {
                        res.push_back(left);
                    }
                    // if right is the last place, we need also remove the left char
                    if(right +1 == left+nP)
                    {
                        char delChar = s[left];
                        if(pFound[delChar] == pM[delChar])
                            matchedChar--;
                        pFound[delChar]--;
                        if(pFound[delChar] == pM[delChar] )
                            matchedChar++;
                        left++;
                    }
                }                
            }
        }
        return res;
    }
};

改进了一下， 利用全是English lowercase letter， 来用array， 或者vector来计算

但是利用了vector对比。 （而不需要计数。  虽然理论上我们的更快）

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/528625/C%2B%2B-94

也可以直接利用unordered_map == 

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/510208/C%2B%2B-unordered-map-Solution

Learned:

we can user vector ==,  (or map ==)