[ 오늘의 코테 연습장 ] [ LeetCode ] 242. Valid Anagram

문제

두 문자열과 t가 주어지면 s의 아나그램이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

Anagram은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어나 구의 문자를 재정렬하여 형성된 단어나 구입니다.`

문제 접근 방식

이 문제는 슬라이딩 윈도우 알고리즘을 활용하여 구현했습니다.

먼저, 두 문자열의 길이를 확인합니다. 길이가 다르다면 그 둘은 절대로 아나그램일 수 없으므로 즉시 false를 반환합니다.
그런 다음 각 알파벳의 등장 횟수를 저장할 두 개의 정수 배열 sChar와 tChar를 생성합니다. 이 배열들은 'a'부터 'z'까지 각 알파벳에 대한 카운트를 저장하게 됩니다.
문자열 't'에 대해, 각 문자가 몇 번 등장하는지 세어 tChar 배열에 저장합니다.
시작 인덱스 si를 0으로 설정하고, 문자열 's'에 대해 동일한 작업을 수행하되, 현재 부분문자열의 길이가 't'와 같아질 때마다 해당 부분문자열과 't'가 아나그램인지 확인합니다.
만약 현재 부분문자열과 't'가 아나그램이라면 true를 반환합니다.
만약 현재 부분문자열과 't'가 아나그램이 아니라면, 해당 부분문자열에서 가장 앞에 있는 문자(즉, s[si])의 카운트를 하나 줄입니다(si 위치에서 시작하는 부분문자열을 이제 고려하지 않기 때문) 그리고 시작 인덱스 si 값을 1 증가시킵니다(다음 위치에서 시작하는 부분문자열로 넘어갑니다).
위 과정을 반복하여 모든 가능한 부분문자열에 대해 검사한 후에도 찾지 못했다면 false를 반환합니다.
여기서 사용된 checkAnagram 함수는 두 개의 정수 배열(즉, 두 개의 알파벳 카운트 배열)이 동일한지 확인하기 위해 사용됩니다.

CODE

class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length()!=t.length()){
            return false; // 만약 s의 문자열 길이가 t보다 작으면, t의 아나그램의 부분 문자열을 포함 할 수 없으므로 false 리턴 
        }
        int[] sChar = new int[26]; // 문자열 s에 대한 문자 카운팅
        int[] tChar = new int[26];// 문자열 t에 대한 문자 카운팅
        
        for(int i = 0  ; i< t.length(); i++){ 
            // 문자열 t의 각 문자의 등장 횟수를 tChar 배열에 저장한다.
            // 각 문자를 int형 index로 변환해서 해당 인덱스의 값을 증가시킨다.
            tChar[t.charAt(i)-'a']+=1; 
            
        }
        // 시작 인덱스 
        int si = 0;
        for(int i = 0 ; i<s.length();i++){
          // 문자열 s의 각 문자의 등장 횟수를 sChar 배열에 저장한다.
        sChar[s.charAt(i)-'a']+=1;
            // 만약 현재 찾은 문자열의 길이 == t 문자열의 길이
            // -> t문자열과 길이가 같은 부분 문자열 찾았을 떄 
            //i는 현재 위치, si는 현재찾고있는 문자열의 시작 위치
            if(i-si+1== t.length()){
                if(checkAnagram(sChar,tChar)){
                   return true;
                }
                // 문자열 s의 시작 인덱스 변경을 위헤 => sChar에서 해당 문자 
                // 등장 횟수 1 감소시키고 시작 인덱스 1 증가
               // sChar[s.charAt(si)-'a']-=1;
              //  si++;
            }
        }
        return false;
    }
    public boolean checkAnagram(int[]sChar, int[] tChar){
        for(int i = 0 ; i < 26; i++){
        if(sChar[i]!=tChar[i]){
            return false;
        }
        }
        return true;
    }
}

다른 접근 방식

다른 접근 방식으로는 HashMap을 이용한 접근 방식이 있었습니다.

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> count = new HashMap<>();
        
        // Count the frequency of characters in string s
        for (char x : s.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        
        // Decrement the frequency of characters in string t
        for (char x : t.toCharArray()) {
            count.put(x, count.getOrDefault(x, 0) - 1);
        }
        
        // Check if any character has non-zero frequency
        for (int val : count.values()) {
            if (val != 0) {
                return false;
            }
        }
        
        return true;
    }
}

제 방식은 공간 복잡도 측면에서는 효율적이였지만, 이 방식보다 코드가 더 복잡하고, 아나그램인지 확인하기 위해 s에서 길이가 t인 모든 부분 문자열을 검사해야합니다.