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로 구현

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