[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.

 

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

 

Constraints:

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

 

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

 

from collections import defaultdict

class Solution(object):
    def isAnagram(self, s_str, t_str):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        dic = {}
        for s in s_str:
            dic[s] = dic.get(s, 0) + 1
        
        for t in t_str:
            if t in dic:
                if dic[t] == 1:
                    del dic[t]
                else:
                    dic[t] -= 1
            else:
                return False
            
        if len(dic) == 0:
            return True
        else:
            return False

s를 저장한 딕셔너리를 하나하나 삭제해가며 확인하는 것. 딕셔너리가 완전히 비어야 하기 때문에 마지막에 len을 이용해서 확인해준다!!!

 

복잡도

time O(N+M) 사실 N과 M이 같을 확률이 높아서 그냥 O(N)으로 봐도 무방할 듯

space O(N)

 

 

정렬해서 같은 리스트인지 확인하는 방법도 있다.

정렬에 O(NlogN), 원소들 비교할 때 == operator의 복잡도는 O(N)이니까 결국 O(NlogN).

 

import collections
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if collections.Counter(s) == collections.Counter(t):
            return True
        else:
            return False

Counter를 사용한 방법. 오호라

 

참고 사이트

https://velog.io/@ahn16/Leetcode-242-Python-Valid-Anagram

Leetcode # 242 (Python): Valid Anagram