Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
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".
Constraints:
1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.
Solution:
Version 1: (template solution)
呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
直接默写一下框架，明确刚才讲的 4 个问题，即可秒杀这道题：
vector<int> findAnagrams(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
vector<int> res; // 记录结果
while (right < s.size()) {
char c = s[right];
right++;
// 进行窗口内数据的一系列更新
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
// 判断左侧窗口是否要收缩
while (right - left >= t.size()) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == need.size())
res.push_back(left);
char d = s[left];
left++;
// 进行窗口内数据的一系列更新
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return res;
}
跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。
Version 2:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int len1 = s.length();
int len2 = p.length();
List<Integer> result = new ArrayList<>();
if(len1<len2) return result;
int[] count = new int[26];
int[] windows = new int[26];
for(int i = 0; i< len2; i++)
{
count[p.charAt(i) - 'a']++;
windows[s.charAt(i) - 'a']++;
}
if(isAnagrams(count,windows))
{
result.add(0);
}
for(int i = 1; i< len1-len2+1; i++)
{
windows[s.charAt(i+len2-1) - 'a']++;
windows[s.charAt(i-1) - 'a']--;
if(isAnagrams(count,windows))
{
result.add(i);
}
}
return result;
}
public boolean isAnagrams(int[] count, int[] windows)
{
for(int i = 0; i< 26; i++)
{
if(count[i]!=windows[i]) return false;
}
return true;
}
}