> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/438.-find-all-anagrams-in-a-string-m.md).

# 438. Find All Anagrams in a String(M)

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 个问题，即可秒杀这道题：

```cpp
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:**&#x20;

```
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;
    }
}
```