[DSA][Array & Hashing] 02. Valid Anagram

LeetCode 241

 

02. Valid Anagram

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

 

 

[질문하기]

- 문자열이 대소문자를 구분해야 하나요?

- 문자열에 알파벳 외에 공백이나 특수문자가 포함될 수 있나요? ex) a b c = abc?

- 빈 문자열이 입력으로 올 수 있나요? 만약 그렇다면, true를 return 해야 하나요?

 

 

[아이디어]

아나그램은 글자의 순서만을 바꿔서 다른 단어를 만드는 것이다. 원래 단어에 포함된 글자를 모두, 한 번씩만 사용해서 만들 수 있는지를 확인해야 한다.

 

 

[풀이 1] Hash using array

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        for val in count:
            if val != 0:
                return False
        return True

소문자 알파벳 이외에 다른 문자가 오지 않는다면 위와 같이 26개짜리 array를 선언한 후 빈도를 세서 array의 모든 값이 0이 되는지를 체크할 수 있다. 하지만 다른 알파벳이 오거나 공백이 포함될 수 있다면, array 대신 hash를 사용해서 각 key의 빈도수를 센 후 두 hash가 같은지 체크하는 것이 더 안전한 방식이다.

 

⏱️ 시간복잡도

Counter는 문자열을 한 번씩 순회하며 빈도를 세기 때문에 시간 복잡도는 O(n)이다.

🧠 공간복잡도

문자열에 등장하는 서로 다른 문자의 개수만큼 공간이 필요하므로 공간 복잡도는 O(k) (k는 서로 다른 문자열의 개수)이다.

k는 최대 26이므로 O(1)이라고 표현할 수 있다.

 

 

[풀이 2] Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

Python에는 해시맵을 사용하여 빈도를 저장하는 내장 Counter 클래스가 있다.

따라서 같은 시간 복잡도, 공간 복잡도를 가지지만 위와 같이 간편하게 사용 가능하다.