[leetcode] 242. Valid Anagram 파이썬 코드

#hash table #string #sorting

 

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        s_hashmap = {}
        t_hashmap = {}

        for alphabet in s:
            if alphabet in s_hashmap: 
                s_hashmap[alphabet] += 1
            else:
                s_hashmap[alphabet] = 1

        for alphabet in t:
            if alphabet in t_hashmap: 
                t_hashmap[alphabet] += 1
            else:
                t_hashmap[alphabet] = 1

        flag = True

        for key, value in s_hashmap.items():
            if key not in t_hashmap:
                flag = False
                break
            else:
                if t_hashmap[key] != value:
                    flag = False
                    break

        if flag == True:
            for key, value in t_hashmap.items():
                if key not in s_hashmap:
                    flag = False
                    break
        
        return flag

 

접근 방법:

s와 t의 hash map을 만들어서 각 알파벳이 몇 개가 나오는지 세서 s와 t hashmap을 비교한다. 

 

더 효율적으로 할 수는 없을까?

(1) 내가 놓친 부분은 두 string의 길이를 비교해보고 길이가 다르면 hash map을 비교할 필요가 없다는 것이다.

if len(s) != len(t):
	return False

 

(2) get() 함수

for alphabet in s:
    if alphabet in s_hashmap: 
        s_hashmap[alphabet] += 1
    else:
        s_hashmap[alphabet] = 1

 

이렇게 했는데 get()을 써서 조금 더 심플하게 쓸 수 있다.

 for i in range(len(s)):
 	s_hashmap[s[i]] = 1 + s_hashmap.get(s[i], 0)

 

(3) s와 t를 한 번에 iterate 시키기

(1)을 해결하기 위해서 두 문자열의 길이를 비교하고 다르면 return False를 했다.

이렇게 했을 때의 장점은 두 문자열의 길이가 같으므로 한번에 s와 t hashmap을 완성할 수 있다는 것이다.

 

for i in range(len(s)):
	s_hashmap[s[i]] = 1 + s_hashmap.get(s[i], 0)
	t_hashmap[t[i]] = 1 + t_hashmap.get(t[i], 0)

 

코드가 훨씬 심플해졌다. 

 

수정한 코드 전체:

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        
        s_hashmap = {}
        t_hashmap = {}

        for i in range(len(s)):
            s_hashmap[s[i]] = 1 + s_hashmap.get(s[i], 0)
            t_hashmap[t[i]] = 1 + t_hashmap.get(t[i], 0)

        for key in s_hashmap:
            if s_hashmap[key] != t_hashmap.get(key, 0):
                return False
    
        return True

 

 

파이썬의 Counter를 사용할 수도 있다!

 

time complexity와 memory complexity가 O(S + T)인데 메모리 복잡도를 O(1)로 만들 수 있는 방법은 없을까?

sorting을 하면 된다!