[leetcode 75] 438. Find All Anagrams in a String

 

문제 해석

문자열 s와 p가 주어졌을 때 p가 s의 anagram인 위치들을 반환하기

위치들의 순서는 상관없음.

 

anagram이란?

모든 원래 문자를 정확히 한 번만 사용하여 재배열해 형성된 단어 또는 구

 

예시

"abc"의 anagram은 "cba", "abc", "bca"등을 말함

 

정답 예

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> output = new ArrayList<>();

    // p의 길이
    int pLength = p.length();
    // s의 길이
    int sLength = s.length();

    if (pLength > sLength) {
        return output;
    }

    // p의 문자 개수를 기록할 배열
    int[] pLetters = new int[26];
    // s의 위치에 따른 부분 문자 개수를 기록할 배열
    int[] sSubletters = new int[26];

    // p의 길이만큼 문자개수 기록
    for (int i=0;i<pLength;i++) {
        pLetters[p.charAt(i) - 'a']++;
        sSubletters[s.charAt(i) - 'a']++;
    }

    for (int i=0;i<sLength-pLength+1;i++) {
        boolean result = true;

        // s의 p길이만큼의 부분 문자열이 Anagrams인지 체크
        // 모든 문자의 개수가 동일하면 true
        for (int j=0;j<26;j++) {
            if (pLetters[j] != sSubletters[j]) {
                result = false;
                break;
            }
        }

        if (result) {
            output.add(i);
        }

        if (i<sLength-pLength) {
            // 검증한 부분문자열의 처음 문자열 제거
            sSubletters[s.charAt(i) - 'a']--;

            // 다음에 검증할 부분문자열의 마지막 문자열만 추가
            sSubletters[s.charAt(pLength + i) - 'a']++;
        }
    }

    return output;
}

이 문제해서 시간복잡도를 줄일 수 있는 부분은 체크할 부분 문자열을 매번 읽어오는게 아니라

기존 검증했던 부분 문자열의 처음을 제거하고 마지막의 다음위치 문자열을 추가 한 뒤 그대로 검증하는 것이다.

 

슬라이딩 윈도우 알고리즘 참고