[LeetCode/Python] 242. Valid Anagram

ㅎㅎ·2024년 4월 26일

leetcode python

LeetCode

목록 보기

32/33

242. Valid Anagram

글자의 순서를 바꾸면 동일한 단어가 되는지를 검사하는 문제다.

Solution 1 : sorted()

sorted() 함수를 사용해 해결했다.
보자마자 가장 처음으로 생각난 방법.

두 문자열을 정렬한 뒤 같은 문자열이 되었는지를 검사한다.

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

시간 복잡도 O(2(nlogn))

sorted() 함수의 시간 복잡도는 O(2(nlogn))이다.

Solution 2 : dictionary

딕셔너리 를 사용해 해결했다.
정렬 함수를 사용하지 않고 해결하는 방법을 생각했을 때 가장 먼저 떠올랐다.
~~딕셔너리만 있으면... 뭐든지 해결할 수 있을 것 같은 기분이다.~~

각 문자열에 대한 딕셔너리를 만들어서 개수를 센다.

s가 가진 문자를 t도 가지고 있는지, 개수가 같은지를 검사한다.

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

        ds = {}
        dt = {}
        l = max(len(s), len(t))
        for i in range(l): # O(n)
            if len(s) > i and s[i] not in ds: ds[s[i]] = 0
            ds[s[i]] += 1
            if len(t) > i and t[i] not in dt: dt[t[i]] = 0
            dt[t[i]] += 1
        
        for d in ds: # O(n)
            if d not in dt or ds[d] != dt[d]: return False
        
        return True

시간 복잡도 O(2n)

각 과정에 대한 시간 복잡도가 각각 O(n)이다.

Solution 3 : Counter

Collection 의 Counter 를 사용해 해결했다.

문자열 s의 요소 개수를 센다.

문자열 t의 요소 개수를 세서 s의 개수에서 뺀다.

빼고 남은 요소가 전부 0인지 검사한다.

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

    count = collections.Counter(s) # 1. O(n)
    count.subtract(collections.Counter(t)) # subtract(): 빼기 # 2. O(n)
    return all(freq == 0 for freq in count.values()) # 3. O(n)