# Find All Anagrams

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.

**문제이해** : String에 Pattern이 있는지, 있다면 몇 번째 인덱스에서 존재하는지 구한다. 

> **Example 1:**\
> **Input :**\
> s : "cbaebabacd" p : "abc"\
> **Output :** \[0,6]
>
> **Example 2:**\
> **Input** :\
> s : "abab" p : "ab"\
> **Output** : \[0,1,2]

**자료구조** : List이용

**알고리즘** : Sliding Window와 배열에 알파벳 아스키코드를 저장하여 비교하는 메커니즘 이용!\
인덱스들을 List에 넣고 이를 리턴한다.\
String과 Pattern 각각에 있는 알파벳 배열을 만들어서 알파벳이있다면 해당하는 배열방의 데이터를 1증가하여 frequency를 기록한다.

**알고리즘을 Java로 구현**

```java
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //1. 담을 그릇 생성
        List<Integer> result = new ArrayList<>();
        //기저사례 제외!
        if(s==null||s.length()==0||p==null||p.length()==0||s.length()<p.length())
		 return result;
        //2.String s와 pattern에 해당하는 알파벳 배열을 생성하여 
        int[] pAlpha = new int[256];
        int[] sAlpha = new int[256];
        
        //2의 frequency를 기록한다.
        for(int i=0; i < p.length();i++) {
            pAlpha[p.charAt(i)]++;
        }
        //3.String s에 patttern의 크기만큼, 1씩 이동한다. i는 시작점,j는 끝점
        for(int i=0; i< s.length()-p.length()+1;i++) {//starting point만 기록할 것이기 때문에 s-p사이즈만큼
            for(int j=0; j<p.length();j++) {//window 크기!
                sAlpha[s.charAt(i+j)]++;
            }
            if(check(pAlpha,sAlpha)){
                result.add(i);
            }
        }
        return result;
    }
    private boolean check(int[] pAlpha, int[] sAlpha) {
        for(int i=0;i<pAlpha.length;i++) {
            if(pAlpha[i] != sAlpha[i])
                return false;
        }
        return true;
    }
}
```