刷题438. Find All Anagrams in a String

一、题目说明

题目438. Find All Anagrams in a String，给一个字符串s和非空字符串p，在s中找到所有p的相同字母异序词的start位置。难度是Medium！

二、我的解答

找同源词，有一个类似的题目49. Group Anagrams,这样的话，本题目也同样的思路。每次从字符串s中截取字符串p长度的字符串，判断是否是同源词。这里用排序后相等的比较方法。

class Solution{
	public:
		vector<int> findAnagrams(string s,string p){
			vector<int> res;

			int lenP = p.size();
			int lenS = s.size();
			if(s.empty() || lenS<lenP) return res;
			
			sort(p.begin(),p.end());
			for(int i=0;i<=lenS-lenP;i++){
				string sub = s.substr(i,lenP);
				sort(sub.begin(),sub.end());
				if(sub.compare(p)==0){
					res.push_back(i);
				}
			}
			return res;
		}
};

然而，运行的结果是：Time Limit Exceeded

三、优化措施

经过分析，超时的原因在于，判断同源词的方法效率太低。用滑动窗口的思想：每次只要字符串s的子串和p中含有相同的字符和数量即可。

class Solution{
	public:
		vector<int> findAnagrams(string s,string p){
			vector<int> res;

			int lenP = p.size();
			int lenS = s.size();
			if(s.empty() || lenS<lenP) return res;
			
			vector<int> hash(26,0),window(26,0);
			for(int i=0;i<lenP;i++){
				hash[p[i]-'a']++;
				window[s[i]-'a']++;
			}
			if(hash==window) res.push_back(0);
			
			for(int i=lenP;i<lenS;i++){
				window[s[i]-'a']++;
				window[s[i-lenP]-'a']--;
				if(hash==window) res.push_back(i-lenP+1);
			}
			return res;
		}
};

性能如下：

Runtime: 28 ms, faster than 94.51% of C++ online submissions for Find All Anagrams in a String.
Memory Usage: 10.3 MB, less than 98.08% of C++ online submissions for Find All Anagrams in a String.