[LeetCode]438. Find All Anagrams in a String

Anagram 이란?

어구전철(語句轉綴) 또는 애너그램(anagram)은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것이다. 어구전철을 잘 아는 사람들끼리 암호문으로 어구전철을 사용할 수도 있지만 그렇지 못할 경우도 많다. 그 이유는 어구전철은 여러 자의적 해석이 가능하기 때문이다. 펩 과르디올라의 대사가 많다.

페프 과르디올라 - 위키백과, 우리 모두의 백과사전

 

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Find All Anagrams in a String - LeetCode

 

이 문제를 풀기 위해서는 char형을 int 형으로 바꿀 수 있다는 점을 알아야 한다.

소문자 알파벳 26자를 int[] 배열에 순서대로 담는 다고 생각하고 문제를 풀 면 된다.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> answer = new ArrayList<>();
        
        int len1 = s.length();
        int len2 = p.length();
        
        int[] arr = new int[26];
        for(int i = 0; i < len2; i++){
            arr[p.charAt(i)-'a']++;
        }
        
        int start = 0;
        
        for(int i = 0; i < len1; i++){
            arr[s.charAt(i)-'a']--;
            
            if(i-start >= len2) arr[s.charAt(start++)-'a']++;
             
            if(isAllZero(arr)) answer.add(start);
            
        }
        
        return answer;
        
    }
    
    public boolean isAllZero(int[] arr){
        for(int i = 0; i < 26; i++){
            if(arr[i] > 0) return false;
        }
        
        return true;
    }
}