Description

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

My solution

最简单的想法就是从1->psize, 2->psize+1, 3->psize+2,... 每次都计算并比较两个map是否一样

考虑到每次只有一个新元素进来,一个旧元素离开,所以算法可以简化为只对变化的地方修正map

又考虑到每次比较两个map全部元素也是冗余的,因为只需要比较变化的地方, 倘若某些元素已经是s<=>p匹配的了,就可以忽略,我采用的方式是建立一个待考察的map(命名为dif), 当dif为空, 则两个map无差异, res.push_back即可; 当dif不为空, 就说明滑窗需要继续前进.这样便省去了每次比较两个map的O(psize)的复杂度.

总的来说基本思路是unordered_map思路, 当然代码有待优化

class Solution {public:    vector
    
      findAnagrams(string s, string p) {        vector
     
       res;        int ssize = s.size();        int psize = p.size();        unordered_map
      
        mp;        for (int i = 0; i < psize; ++i) --mp[p[i]];        unordered_map
       
         dif = mp;        for (int i = 0; i < psize; ++i) {            if (++dif[s[i]] == 0) dif.erase(s[i]);        }        if (dif.empty()) res.push_back(0);        for (int i = psize; i < ssize; ++i) {            if (++dif[s[i]] == 0) dif.erase(s[i]);            if (--dif[s[i - psize]] == 0) dif.erase(s[i - psize]);            if (dif.empty()) res.push_back(i - psize + 1);        }        return res;    }};

Discuss

下面代码和我的思路基本一致, 不过因为字母连续有限, 直接用26个空间的vector存储(这是特例情况下的操作). 当然vector的存取时间消耗应该是更高的, 尤其是下文代码中p==v的步骤.

class Solution {public:    vector
    
      findAnagrams(string s, string p) {        vector
     
       pv(26,0), sv(26,0), res;        if(s.size() < p.size())           return res;        // fill pv, vector of counters for pattern string and sv, vector of counters for the sliding window        for(int i = 0; i < p.size(); ++i)        {            ++pv[p[i]-'a'];            ++sv[s[i]-'a'];        }        if(pv == sv)           res.push_back(0);        //here window is moving from left to right across the string.         //window size is p.size(), so s.size()-p.size() moves are made         for(int i = p.size(); i < s.size(); ++i)         {             // window extends one step to the right. counter for s[i] is incremented             ++sv[s[i]-'a'];                        // since we added one element to the right,             // one element to the left should be forgotten.             //counter for s[i-p.size()] is decremented            --sv[s[i-p.size()]-'a'];             // if after move to the right the anagram can be composed,             // add new position of window's left point to the result             if(pv == sv)                 res.push_back(i-p.size()+1);        }        return res;    }};