May LeetCoding Challenge[Day17] - Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.

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

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 긴 문자열인 s와 짧은 문자열인 p가 주어질 때, s에서는 p의 아나그램을 어느 인덱스와 인덱스에 갖고 있느냐에 관련된 문제였습니다.

 - 3주차 너무 어렵다고 느끼면서 딜레이되고 있지만, 꾸준하게 진행을 했습니다.

 - 우선, 아나그램이 성립되는 조건은 짧은 문자열의 길이에서 나오는 각 문자의 갯수와 긴 문자열에서 짧은 문자열만큼 길이를 잘랐을 때, 각 문자의 갯수가 같다면 아나그램이 성립됩니다.

 - 그러면, s의 입력 문자열을 p의 문자열의 길이만큼 검사하면서 1칸씩 이동해서, 모두 탐색하면 정답을 얻을 수 있습니다.

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

- 해당 문제를 풀면서 어려웠던 점은 s문자열에서 1칸 이동할 때, sMap에 데이터를 어떻게 쌓으면서 이동하는 것이 어려웠습니다.

 - 아나그램인지 확인하기 위해서 pMap의 길이만큼 sMap과 pMap의 아이템을 비교합니다.

즉 알파벳의 길이인 26만큼 pMap과 sMap의 모든 인덱스의 모든 아이템을 비교하는데, 알고리즘을 처음 접근할 때는 for(int i=0; i<p.length(); i++){pMap[p.charAt(i)-'a'] == sMap[s.charAt(i)-'a']} 이 p의 문자열 길이만큼만 검사하기 때문에 효율적이라고 생각했는데, 그렇지 않다는 것을 알게 되었습니다.

 

3. 내가 작성한 알고리즘

 

 

 

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> array = new ArrayList();
        short[] pMap = new short['z' -'a' + 1];//소문자 알파벳의 길이만큼 배열을 생성
        short[] sMap = new short['z' -'a' + 1];//소문자 알파벳의 길이만큼 배열을 생성

        if(s.length() < p.length()){ //1. s의 문자열이 p보다 짧으면 빈 값을 되돌려줌
            return new ArrayList();
        }
        
        //검사할 p 문자열을 pMap으로 하여, 각 문자의 아스키코드를 키 값으로 접근함
        for(int i=0; i<p.length(); i++){
            pMap[p.charAt(i)-'a']++;
        }
        
        boolean isEqauls = true;

        //sMap도 동일하게 하는데 p의 문자열 길이만큼만 만들어줘서 한 번의 검사만 실행해줌
        //O(M)
        for(int i=0; i<p.length(); i++){
            sMap[s.charAt(i) - 'a']++;
        }
        //O(M)
        for(int i=0; i<pMap.length; i++){
            if(pMap[i] != sMap[i]){
                isEqauls = false;
                break;
            }
        }
        if(isEqauls){
            array.add(0);
        }
    
    	//한 번 실행 후에는 s가 "abcde" 라면 기존에 "abc"만큼 값을 검사했으므로
        //"bcd"의 검사를 위해서 "a"의 값을 내리고, "d"의 값을 올리는 로직으로
        //O(N)을 검사하게 함
        for(int i=p.length(); i<s.length(); i++){
            isEqauls = true;
            sMap[s.charAt(i-p.length()) - 'a']--;
            sMap[s.charAt(i) - 'a']++;
            //pMap과 sMap을 알파벳의 길이 O(26) 만큼 검사함
            for(int j=0; j<pMap.length; j++){
                if(pMap[j] != sMap[j]){
                    isEqauls = false;
                    break;
                }
            }
            if(isEqauls){
                array.add(i-p.length()+1);
            }
        }
        
        //O(M) + O(M) + O(N) + O(26) = O(N)이 제일 크므로, O(N)의 시간복잡도를 갖게 됨
        return array;
    }
}

 

4. 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3332/

Explore - LeetCode