Sliding Window (fixed length)
比较straightforward的方法,用长度为p的window去扫描,判断两个hashtable统计结果是否相同。在不清楚C++里unordered_map有没有重载==的情况写,可以用两个vector来做counter。
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; if (s.size()<p.size()) return res; vector<int> sc(256), pc(256); // s count and p count for (int i=0;i<p.size();++i){ ++sc[s[i]]; ++pc[p[i]]; } if (sc==pc) res.push_back(0); for (int i=1;i<=s.size()-p.size();++i){ //all possible start points // delete s[i-1], add s[p.size()-1+i] --sc[s[i-1]]; ++sc[s[p.size()-1+i]]; if (sc==pc) res.push_back(i); } return res; } };
Sliding Window (General)
Sliding Window 模板写法,用一个hashtable记录所需字符的个数,还需要一个count判断窗口中已经有多少p中的字符。
如果count等于t.size(),说明当前窗口的字串包含p里所有的字符了。此时需要额外判断窗口大小是否等于p的size,如果相等,那么start就是一个答案。
参考 LeetCode 76. Minimum Window Substring / 567. Permutation in String / Share Purchases
class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<int,int> hash; // number of char needed for (char ch:p) ++hash[ch]; int count=0; int start=0; vector<int> res; for (int i=0;i<s.size();++i){ if (--hash[s[i]]>=0) ++count; while (count==p.size()){ if (i-start+1==p.size()) res.push_back(start); if (++hash[s[start]]>0) --count; ++start; } } return res; } };