[LeetCode] 242. Valid Anagram

문제

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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.

242. Valid Anagram는 문자열 s와 t가 주어졌을때 t가 s의 아나그램, 즉 s의 순열 중 하나인지 판단하는 문제다.

여기서 문자열은 ASCII 코드로 이루어져 있다고 가정한다.

BCR(Best Conceivable Runtime)

s와 t의 모든 문자를 한 번씩은 확인해야 하기 때문에, BCR은 s와 t의 길이가 각각 $N$, $M$이라고 할 때 $O(N+M)$이다.

풀이 1

첫 번째로 생각할 수 있는 방법은 완전 탐색이다. s의 모든 순열을 만들어가면서 해당 순열이 t와 동일한지 판단하는 방법이다. 해당 방법의 시간 복잡도는 $O(N!)$이기 때문에, s의 길이가 11을 넘어가는 경우 문제를 거의 풀 수 없다. 그러나 본 문제의 s의 길이 제한은 $5\times10^4$이기 때문에 이 방법은 사용할 수 없다.

풀이 2

두 번째 방법은 s와 t를 정렬한 후 이들이 동일한지 판단하는 방법이다. 여기서, 만약 s와 t의 길이가 다르다면 이는 절대 문제의 조건을 충족하지 못하므로 길이의 동일 여부에 대해 먼저 검사한다.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        for (int i = 0; i < s.length(); i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}

본 방법의 전체 시간 복잡도는 정렬에 의존하므로 평균적으로 $O(NlogN)$이다. 공간 복잡도의 경우 자바의 String은 불변 객체(Imuutable Object)이기 때문에 s와 t를 배열로 만드는 과정이 필요하므로 $O(N$)이다.

풀이 3

세 번째 방법은 각 문자의 등장 횟수를 기록하는 방법이다. 문제에서 모든 문자는 알파벳 소문자라고 했으므로 길이가 26인 refCnts 배열을 선언한 다음 s와 t를 탐색하면서 등장 횟수를 기록한다. 이때 s에서 등장하는 문자는 +1, t에서 등장하는 문자는 -1을 한다. 그리고 마지막에서 refCnts의 원소가 모두 0인지 판단한다. 이는 s에서 등장하는 문자들이 t에서 똑같은 횟수로 등장한다는 것을 의미한다.

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

이 방법의 시간 복잡도는 선형 탐색만을 수행하므로 $O(N)$, 공간 복잡도는 refCnts가 있지만 길이가 26으로 상수이기 때문에 $O(1)$이다.

Follow up

만약 문자열이 유니코드로 이루어져 있다면 어떻게 해야할까? 유니코드는 2 Bytes로 문자를 표현하기 때문에, 65536개의 문자를 표현할 수 있다. 그러므로 refCnts의 길이를 $2^{16}$인 65536로 늘리고 idx를 다음과 같이 구한다.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] refCnts = new int[65536];
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i);
            refCnts[idx] += 1;
            idx = t.charAt(i);
            refCnts[idx] -= 1;
        }
        for (int refCnt: refCnts) {
            if (refCnt != 0) return false;
        }
        return true;
    }
}

참고로 자바는 유니코드로 문자를 표현한다. 즉 char 형이 2 Bytes를 차지한다.