[LeetCode] 242. Valid Anagram

Intuition

• Anagram은 주어진 문자열의 character를 재배치 했을 때에도 다 같은 구성의 character를 가지는 단어 혹은 문구를 뜻한다고 한다. 
  • 그러니 길이가 같아야지? 
• 같은 구성의 character를 가져야하겠네?

Approach

• 같은 구성의 문자를 가진것을 어떻게 비교하면 좋지? 
  • 정렬한 후에 같은지 확인하면 효율적이지 않을까
• 길이가 다른 경우는 먼저 False를 반환 하는게 좋을 것 같다 

Complexity

Time complexity:

• O(nlogn) 평균 / W.C (= worst case) 
  • 이유는 python의 sorted() 함수는 Timesort라는 정렬 알고리즘을 사용 
  • Timesort 알고리즘이란? 
    • insertion sort 와 merge sort의 장점만을 합쳐서 만든 hybrid sorting algorithm  
    • 평균 & W.C = O(NlogN) 을 보장 
    • 참고: https://realpython.com/sorting-algorithms-python/#the-timsort-algorithm-in-python

Space complexity:

• O(1) 평균 / O(n) W.C 

Code

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