解题思路:
\qquad 这个题目解法没什么特别的,遍历所有子串,比较与目标字符串是否满足异位词即可。唯一需要注意的是,提示s
和p
仅包含小写字母,且异位词不关心字符的顺序,可以使用长度为26的数组,通过记录26个字母的个数来比较,减少时间复杂度。
vector<int> findAnagrams(string s, string p) {vector<int> aim(26);vector<int> curr(26);vector<int> res;if(s.length() < p.length()) return res;for(int i = 0; i < p.length(); i++){aim[p[i] - 'a']++;curr[s[i] - 'a']++;}if(aim == curr){res.push_back(0);}for(int n = 0; n < s.length() - p.length(); n++){curr[s[n+p.length()] - 'a']++;curr[s[n] - 'a']--;if(curr == aim){res.push_back(n+1);}}return res;}