LeetCode 풀기 - 49. Group Anagrams

49. Group Anagrams

https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

문제)

솔루션1) hash

strs에 있는 단어 각각에 대해서 hash 값을 생성합니다.

hash 값이 동일하다면 동일한 anagram에 속합니다.

 

예를 들어, 아래와 같이 eat와 ate을 동일한 hash key이므로 동일한 그룹에 속하는 anagram입니다.

hash key를 생성할 때는 알파벳순, count순 오름차순 정렬을 합니다.

word	hash key
eat	a1e1t1
ate	a1e1t1
bat	a1b1t1

 

풀이를 정리하자면,

1) 해쉬맵 생성 (key=hash key, value=[단어들])

1) 각 단어에 대에서 hash key를 생성

2) hash key와 단어를 해쉬맵에 추가

3) 해쉬맵의 vaues는 group anagrams로 묶임

 

 

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        def get_hash_key(word):
            """
            get hash key from word            
            ex) eat
            e -> 1
            a -> 1
            t -> 1
            hash key = a1e1t1
            """
            # key=alphabet, value=count
            counter = Counter(word)
            
            # dict to list
            counter = list(counter.items())
            
            # sorting by alphabet, count
            counter = sorted(counter, key=lambda x: (x[0], x[1]))
            
            keys = []
            for c, count in counter:
                keys.append(c)
                keys.append(str(count))
            return ''.join(keys)
            
        
        d = defaultdict(list)
        for word in strs:
            key = get_hash_key(word)
            d[key].append(word)
        return list(d.values())

솔루션2) sorted(), defaultdict()

tuple 오브젝트는 hash map의 key로 사용할 수 있다는 특징을 이용합니다.

class Solution(object):
    def groupAnagrams(self, strs):
        strs = sorted(strs)
        d = defaultdict(list)
        for word in strs:
            key = tuple(sorted(word))
            d[key].append(word)
        return list(d.values())