LeetCode (438) - Find All Anagrams in a String

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Find All Anagrams in a String

• Acceptance: 47.6%
• Difficulty: Medium

문제 설명

String s와 p가 주어진다. p의 anagram과 일치하는 모든 s의 substring의 시작 index를 list로 return. 순서는 중요하지 않다.

anagram이란 단어가 재배열되어서 순서가 다르지만 구성하는 요소가 같은것을 의미한다.

예시 1

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

예시 2

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

문제 풀이

• 조건에 문자열 s가 p보다 항상 크다는 조건이 없으므로 p의 길이가 더 큰 경우 바로 return.

• a - z를 담을 수 있는 배열 array를 생성 후, 문자열 p의 문자를 array의 해당 값에 +1을 한다. 그 후 문자열 s의 substring을 (0, p.length) 만큼의 원소를 array의 해당 값에 -1 한다. 즉, array의 모든 값이 0이라면 이는 anagram이다. 이때 substring의 start index를 head변수에 저장한다.

• 다음 문자열이 anagram인지 확인하기 위해서 s.charAt(head) 값을 다시 +1 해주고 s.chartAt(p.length + 1)에 해당 하는 값을 -1한 후 anagram인지 확인.

• 위 과정을 p.length + i < s.length() 일 때까지 반복한다.

코드

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

class Solution {
    private int arrayLength = 'z' - 'a' + 1;

    private boolean isAnagram(int[] array) {
        for (int i = 0; i < arrayLength; i++) {
            if (array[i] != 0) {
                return false;
            }
        }
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        int head = 0;
        List<Integer> result = new ArrayList<>();
        int[] array = new int[arrayLength];
        
        // 문자열 p가 s보다 길다면 return
        if (p.length() > s.length()) {
            return result;
        }
        
        // array에 문자열 p의 원소는 +1, s.substring의 원소는 -1
        for (int i = 0, pLength = p.length(); i < pLength; i++) {
            array[p.charAt(i) - 'a']++;
            array[s.charAt(i) - 'a']--;
        }
        
        // anagram인지 확인
        if (isAnagram(array)) {
            result.add(head);
        }
        
        // 한칸씩 이동하며, 이전에 빼준 head에 해당하는 원소값은 +1, 다음 해당하는 원소값은 -1
        for (int i = p.length(); i < s.length(); i++) {
            array[s.charAt(head) - 'a']++;
            head++;
            array[s.charAt(i) - 'a']--;

            // anagram인지 확인
            if (isAnagram(array)) {
                result.add(head);
            }
        }

        return result;
    }
}