[LeetCode/MEDIUM] 438. Find All Anagrams in a String (JAVA) : 문제&풀이

 

 

패턴String의 애너그램에 해당하는 시작 index 리스트를 반환하는 문제이다.

두 개의 String을 매개변수로 받는 findAnagrams 메서드의 틀이 주어진다.

 

Problem :

public class FindAllAnagramsInAString {
    public List<Integer> findAnagrams(String s, String p) {

    }
}

풀이는 findAnagrams 메서드에 작성하면 된다.

 

Solution :

1. 패턴(p)에 해당하는 Ascii값이 1인 int배열을 통해서 푼다.
2. 오른쪽 포인터가 배열 길이 이내인 동안 반복문을 돌며 Sliding Window 방식으로 푼다.
   1. 오른쪽 포인터에 해당하는 Ascii가 0보다 크면 패턴이 있는 것이므로, 해당 배열값을 줄이고 포인터와 count를 늘린다.
   2.  아닌 경우, 패턴이 없는 것이므로 왼쪽 포인터와 해당 배열값을 늘리고 count를 줄인다.
      (없는 패턴의 배열값을 증가시키더라도 count가 줄기 때문에 매치되지 않는 것으로 치부된다.)
   3. count가 패턴길이와 같아지면 그 때의 왼쪽 포인터를 결과 리스트에 추가한다.
3. 반복문이 끝나면 결과 리스트를 반환한다.

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

public class FindAllAnagramsInAString {

    // time complexity : while loop (sliding window) -> O(n)
    // space complexity : constant char array -> O(1)
    public List<Integer> findAnagrams(String s, String p) {
        if(s == null || s.length() == 0 || p == null || p.length() == 0) return new ArrayList<>();

        int[] patternAscii = new int[256];
        for(char c : p.toCharArray()){
            patternAscii[c] = 1;
        }

        List<Integer> result = new ArrayList<>();
        int left = 0, right = 0, count = 0;
        while(right < s.length()){
            if (patternAscii[s.charAt(right)] > 0) {
                patternAscii[s.charAt(right)]--;
                count++;
                right++;
            } else {
                patternAscii[s.charAt(left)]++;
                count--;
                left++;
            }

            if(count == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

 

위 과정을 그림으로 도식화하면 다음과 같다.

 

Complexity :

• 시간복잡도 (Time Complexity)
  • Sliding Window 방식으로 반복문이 오른쪽으로만 진행하므로 O(n)
• 공간복잡도 (Space Complexity)
  • ASCII코드가 표현된 char 배열이 주어진 문자열과 상관없이 고정적으로 사용되므로 O(1)

 

Sample(Test) :

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

public class FindAllAnagramsInAString {

    // time complexity : while loop (sliding window) -> O(n)
    // space complexity : constant char array -> O(1)
    public List<Integer> findAnagrams(String s, String p) {
        if(s == null || s.length() == 0 || p == null || p.length() == 0) return new ArrayList<>();

        int[] patternAscii = new int[256];
        for(char c : p.toCharArray()){
            patternAscii[c] = 1;
        }

        List<Integer> result = new ArrayList<>();
        int left = 0, right = 0, count = 0;
        while(right < s.length()){
            if (patternAscii[s.charAt(right)] > 0) {
                patternAscii[s.charAt(right)]--;
                count++;
                right++;
            } else {
                patternAscii[s.charAt(left)]++;
                count--;
                left++;
            }

            if(count == p.length()) {
                result.add(left);
            }
        }

        return result;
    }

    public static void main(String[] args){
        String s1 = "cbaebabacd";
        String p1 = "abc";
        String s2 = "abab";
        String p2 = "ab";

        FindAllAnagramsInAString f = new FindAllAnagramsInAString();
        System.out.println(f.findAnagrams(s1, p1));
        System.out.println(f.findAnagrams(s2, p2));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[0, 6]
[0, 1, 2]