[Leet Code] 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.

 

Anagram

문자의 위치를 바꿨을 때 다른 뜻을 가진 단어로 바꾸는 것을 의미한다.

 

Solve

입력값으로 문자열을 담은 배열이 주어진다.

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

 입력값 중에 Anagram이 같은 것인 문자열만으로 그룹을 지어 다음과 같이 리턴해야 한다.

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

문제를 어떻게 풀까 생각하다 보니 정렬하여 비교해보는 방법이 떠올랐다.

from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        answer = {}
        result = []

        # Key initialized
        for x in set(''.join(sorted(x)) for x in strs):
            answer[x] = []

        for word in strs:
            sortword = ''.join(sorted(word))

            if sortword in answer:
                answer[sortword].append(word)

        for k, v in answer.items():
            result.append(v)

        return sorted(result)

아래는 Submission이다.

 

Runtime: 104 ms, faster than 60.36% of Python3 online submissions for Group Anagrams.

Memory Usage: 17.6 MB, less than 64.32% of Python3 online submissions for Group Anagrams.

 

Other Way

다른 풀이는 어떤 게 있을까하고 구글링에서 좀 찾아봤다. 다음과 같이 defaultdict를 이용해서 풀이하는 방법도 존재했다. 

from collections import defaultdict

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:        
    anagram = defaultdict(list)

    for word in strs:
        anagram[''.join(sorted(word))].append(word)

    return list(anagram.values())

defaultdict를 이용하니 내가 풀었던 코드보다 간결해졌다. submission은 어떨까?

 

Runtime: 92 ms, faster than 93.05% of Python3 online submissions for Group Anagrams.

Memory Usage: 17.3 MB, less than 77.67% of Python3 online submissions for Group Anagrams.

 

Runtime을 보니 더 효율적인 코드인게 확실한 것 같다.