LeetCode 242(Valid Anagram, java)

0. 문제

https://leetcode.com/problems/valid-anagram/

Valid Anagram - LeetCode

 

1. 문제 설명

- 문제에서 2개의 문자열(s, t)이 주어진다.

- 문자열 t가 문자열 s의 아나그램인지 판별하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 각 문자열의 길이를 구한다.

- 만약 길이가 동일하지 않다면 아나그램이 될 수 없다. 

 

b) 두 번째 접근

- 각 문자열을 구성하는 문자의 종류와 개수를 파악해야 한다.

- 이를 위해 26의 길이를 가지는 alphabet이라는 정수형 배열을 생성한다.

- alphabet 배열의 각 index는 각 알파벳을 의미하며, 등장 횟수가 요소로 기록된다. 

 

c) 세 번째 접근

- 비교의 기준이 되는 문자열을 하나 정한다. (t, s 아무거나 상관없다.)

- for 문을 반복하여 기준이 되는 문자열을 순차적으로 탐색한다.

- 이때 문자열 연산을 이용하여 alphabet 배열의 index 위치를 계산한다.

- 연산 결과를 index로 사용하여 alphabet 배열의 해당 index에 위치한 요소를 1씩 증가시킨다.

 

- 비교의 대상이 되는 문자열 또한 위와 같은 방식을 사용한다.

- 다만, 해당 index에 위치한 요소를 1씩 감소시킨다.

 

d) 네 번째 접근

- 마지막으로 alphabet 배열의 각 요소를 탐색하면서 0이 아닌 값이 있는지 확인한다.

- 모든 요소가 0이라면 아나그램이다.

- 0이 아닌 요소가 하나라도 있다면 아나그램이 아니다.

 

- 위의 문제는 26개의 공간을 가진 alphabet 배열만으로 해결한다는 점에서 굉장히 효율적인 솔루션이다.

- 다음 코드를 보면서 이해해보자.   

 

3. 정답 코드

class Solution {
    public boolean isAnagram(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        
        if (sLen != tLen) {
            return false;
        }
        
        int[] alphabet = new int[26];
        
        for(int i = 0; i < sLen; i++) {
            alphabet[s.charAt(i) - 'a'] ++;
        }
        
        for(int i = 0; i < tLen; i++) {
            alphabet[t.charAt(i) - 'a'] --;
        }
        
        for(int num : alphabet) {
            if(num != 0) {
                return false;
            }
        }
        
        return true;
    }
}