# 438. Find All Anagrams in a String

&#x20;[**438. Find All Anagrams in a String**](https://leetcode.com/problems/find-all-anagrams-in-a-string/description/)

Given a string **s** and a **non-empty** string **p**, find all the start indices of **p**'s anagrams in **s**.

Strings consists of lowercase English letters only and the length of both strings **s** and **p** will not be larger than 20,100.

The order of output does not matter.

**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".
```

***My Solutions:***

anagram 的定义是两个单词里出现的字母相同。

方法1：naive，把string里每一个char的len = p的substring都检查一遍

Time: O(n), n = length of s

```
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() == 0 || p.length() == 0) return res;
        
        int len = p.length();
        for (int i = 0; i <= s.length() - len; i++) {
            if (isAna(s.substring(i, i + len), p)) {
                res.add(i);
            }
        }
        
        return res;
    }
    
    private boolean isAna(String s, String p) {
        int[] hash = new int[26];
        for (int i = 0; i < p.length(); i++) {
            hash[p.charAt(i) - 'a']++;
            hash[s.charAt(i) - 'a']--;
        }
        for (int c : hash) {
            if (c != 0) return false;
        }
        return true;
    }
}
```

方法2：

* 先创建一个256大小的int array，把p里所有字符出现的频率记录下来。用counter记录p的长度
* 然后用两个指针，left代表sliding window的左边，即单词的开始index，right向右移动创造sliding window。只要right没有到搜索s的最末端，就不停向右移动。
  * 在移动的过程中，right所在的字符如果在p里，就把counter 减1。
  * 检测counter是否为0。如果为0，说明p里的所有字符都已经找到，把left此时的数字加入结果。
  * 无论如何，right所在的字符在int array里的频率减1。然后移动right，right++。
  * 如果此时left和right之间的距离等于p的长度，说明window已经是p的长度。我们需要把left左移，让window继续前进。
    * 首先看此时int array里left所在的数字。如果此数字大于等于0，说明l所在的这个字母在p里出现过，因为没有出现过的字母会是负数。之前counter在这个情况下减去过1，所以此时count++把这个1加回来。
    * 无论如何要把int array里的left所在的字符频率也+1。left再右移，left++。

```
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() == 0 || p.length() ==0) return res;
        
        // 记录p里letter出现的频率
        int[] hash = new int[256];
        for (char c : p.toCharArray()) hash[c]++;
        
        //counter is a number to record whether we have a anagram which has equal length as p
        int left = 0, right = 0, counter = p.length(); 
        
        while (right < s.length()) {
            
            // there is p's char in s，把counter减少1
            char curr = s.charAt(right);
            if (hash[curr] >= 1) counter--;
            
            // 如果counter==0，说明每个在p里的字母都在s里找到了
            if (counter == 0) res.add(left);
                
            // hash table decreases the right char by 1    
            hash[curr]--;    
            right++; //move the sliding window to one step right
            
            //if the window's size equals p, then we have to move left (narrow the window) to find the new match window
            if (right - left == p.length()) { 
                // only increase the count if the character is in p，因为之前只有这样的条件才会count--      
                if (hash[s.charAt(left)] >= 0) counter++;
                // 因为之前减少过hash[curr]--, 马上要移动left坐标，所以这里需要加1回来
                hash[s.charAt(left)]++; 
                left++;
            }
        }
        
        return res;
    }
}
```
