[LeetCode] 438. Find All Anagrams in a String - 문제풀이

Description

s의 문자열에 p문자열의 아나그램이 적용되는 모든 인덱스를 반환하는 문제입니다.

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.

Example 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".

Example 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".

Constraints:

• 1 <= s.length, p.length <= 3 * 104
• s and p consist of lowercase English letters.

Solution 1. sliding window

public List<Integer> findAnagrams(String s, String p) {
    //1. sliding window
    List<Integer> result = new ArrayList<>();
    int len1 = s.length();
    int len2 = p.length();
    int[] map = new int[26];
    for (int i = 0; i < len2; i++) {
        map[p.charAt(i)-'a']++;
    }
    int start = 0;
    for (int i = 0; i < len1; i++) {
        map[s.charAt(i)-'a']--;
        if(i-start >= len2){
            map[s.charAt(start++)-'a']++;
        }
        if(isAllZero(map)){
            result.add(start);
        }
    }
    return result;
}

private boolean isAllZero(int[] map){
    for (int i = 0; i <map.length ; i++) {
        if(map[i] != 0) return false;
    }
    return true;
}

배열을 영어 소문자 26개를 저장하는 Hash Table로 이용하여 슬라이딩 윈도우 알고리즘을 통해 카운팅해가며 일치 할때마다 해당 인덱스를 반환해 줍니다.

Reference

Find All Anagrams in a String - LeetCode