개요

LeetCode #49, Group Anagrams 문제를 풀어봅니다.

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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: 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”]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

strs의 각 원소를 정렬한 것을 key로 하는 딕셔너리를 만들고, 딕셔너리의 value로 anagram들을 넣을 것입니다. collections 라이브러리로 defaultdict를 만들어주고, strs의 각 원소들을 word로 하여 그 word를 정렬 후 리스트로 반환되니 join으로 리스트를 깨 줍니다. 그것을 key로 하여 딕셔너리로 만들고 value를 리스트로 돌려주면 됩니다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # sorting each element of strs, make a dictionary
        
        # if a key is not exist: keyerror --> need a default one 
        # --> defaultdict in collections library
        # defaultdict(list, {})
        anagrams = collections.defaultdict(list)
        
        for word in strs:
            # sort -> dictionary: if word is 'eat' then 
            # {'ate': ['ate','eat','tea',...]}
            # sorted returns a list --> use ''.join()
            # sorted('ate') -> ['a','e','t'] -> 'aet'
            anagrams[''.join(sorted(word))].append(word)
            
        return list(anagrams.values())