[Leetcode] 438. Find All Anagrams in a String

모든 Anagram을 찾는 문제입니다.

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

Find All Anagrams in a String - LeetCode

이 문제는 sliding window 알고리즘을 사용하는 대표적인 문제 중 하나입니다.

어떻게든 노가다로 문제를 풀 수는 있지만 sliding window를 사용하지 않는다면 좋은 성능으로 풀기 어려운 문제입니다.

 

anagram이란 알파벳의 종류와 갯수가 서로 같은 두 문자열로 해석할 수 있습니다.

알파벳은 총 26자입니다.

즉, 26개크기의 배열만 있으면 문자열에 존재하는 각 알파벳들의 총 갯수를 저장해놓을 수 있습니다.

저는 countArr이라는 배열을 선언해놓고 알파벳의 종류와 갯수를 저장할 목적으로 사용했습니다.

 

step1.

p의 알파벳에 대해서는 countArr에 빼주고, s에 존재하는 알파벳에 대해서는 countArr에서 더해주었습니다.

만약 countArr에 모든 값이 0이 된다면..?

바로 anagram을 의미하게 됩니다.

 

step2.

step1에서 체크했던 부분 이후부터 s 문자열을 끝까지 체크해봅니다.

left는 배열의 시작, right는 배열의 마지막이라고 보면 됩니다.

시작점이 우측으로 이동됨에 따라,

시작점에 있는 문자는 더이상 체크하지 않을 문자가 되게 되므로 countArr에서 빼주고, 

마지막점에 해당하는 문자는 새롭게 체크할 문자가 되므로, countArr에서 더해줍니다.

만약에 countArr의 모든 수가 0이된다면 anagram이 됩니다.

class Solution {
  public List<Integer> findAnagrams(String s, String p) {
    if (p.length() > s.length()) return new ArrayList<>();
    char[] sChars = s.toCharArray();
    char[] pChars = p.toCharArray();
    int[] countArr = new int[26];

    for (int i = 0; i < p.length(); i++) {
      countArr[pChars[i]-'a']--;
      countArr[sChars[i]-'a']++;
    }

    List<Integer> anagrams = new ArrayList<>();
    if(findAnagram(countArr)) anagrams.add(0);

    for (int i = p.length(); i < s.length(); i++) {
      int left = i - p.length();
      int right = i;
      countArr[sChars[left]-'a']--;
      countArr[sChars[right]-'a']++;

      if(findAnagram(countArr)) anagrams.add(left + 1);
    }
    return anagrams;
  }

  public boolean findAnagram(int[] countArr) {
    for(int val : countArr) if(val > 0) return false;
    return true;
  }
}