Find All Anagrams in a String

🔗 문제 링크

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

🔍 문제 설명

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.

⚠️ 제한사항

• $1 <= s.length, p.length <= 3 * 10^4$

• s and p consist of lowercase English letters.

🗝 풀이 (언어 : Java)

처음에 for문을 한번 돌리고 안에서 Arrays.sort를 이용해서 anagram을 판별하는 알고리즘으로 풀었다. 통과는했지만 시간복잡도가 매우 높게 나왔고, 이 문제의 모범답안은 Sliding Window 기법이라는 것을 알았다. 풀이를 보고 다시 작성해보았다. 코드를 이해하는게 어려웠지만 계속 보다보니까 감이 조금은 잡힌 것 같다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> answer = new ArrayList<>();
        int left = 0, right = 0, count = p.length();
        // 알파벳 별 개수 카운트
        int[] alphabet = new int[26];
        for (int i = 0; i < p.length(); i++)
            alphabet[p.charAt(i)-'a']++;
        // Slding Window 방식의 투포인터
        while (right < s.length()) {
            // s의 글자가 anagram 타겟 문자열에 포함된 문자이면 찾을 개수 -1
            // 알파벳 배열에서도 해당 글자 횟수 차감, 오른쪽 인덱스 전진
            if (alphabet[s.charAt(right)-'a']-- >= 1)
                count--;
            right++;
            // anagram 비교 가능한 상태면 비교해서 정답 넣어줌
            if (count == 0)
                answer.add(left);
            // 단어 개수가 다 찼으면, 창을 오른쪽 이동하면서 왼쪽 인덱스의 글자가 anagram 해당 글자면 배열에서 해당 글자와 count를 다시 +1
            if (right-left == p.length()) {
                if (alphabet[s.charAt(left) - 'a']++ >= 0)
                    count++;
                left++;
            }
        }
        return answer;
    }
}