[리트코드(LeetCode)] 49번 Group Anagrams

문제

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

Group Anagrams - LeetCode

문자열 배열을 받아 애너그램(문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것) 단위로 그룹핑하라는 문제다.

예시

Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:
Input: strs = [""] Output: [[""]]

Example 3:
Input: strs = ["a"] Output: [["a"]]

풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 리스트 저장하기 위한 defaultdict 생성
        anagrams = collections.defaultdict(list)

        for word in strs:
            # 현재 단어를 문자 정렬 후 키로 사용하여 값(단어) 추가
            anagrams[''.join(sorted(word))].append(word)
        
        return list(anagrams.values())

 

- 애너그램을 판단하기 위해 문자열을 정렬 후 이를 key로 하는 딕셔너리로 구성한다.

 

* 딕셔너리는 [key : value] 형태로 존재하지 않는 key값에 접근하면 에러가 발생한다. defaultdict 를 사용하면 딕셔너리의 존재하지 않는 key 값을 항상 0으로 자동 초기화하므로 에러가 발생하지 않는 장점이 있다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview