[LeetCode][Python] 49. Group Anagrams

- 문제 링크: https://leetcode.com/problems/group-anagrams

- 난이도: Medium

 

주어진 문자열 리스트를 애너그램끼리 묶는 문제다. 예를 들어 eat tea bat 이렇게 주어질 때 (eat, tea) (bat) 이렇게 묶으면 된다

 

두가지 방법이 있다

(1) 모든 단어를 정렬해서 동일한 것끼리 묶는다 - 시간복잡도는 O(m * nlogn) (m: 글자수, n: 문자열 개수)

(2) 각 단어별 히스토그램을 만들고, 히스토그램 동일한것끼리 묶는다 - 시간복잡도는 O(m*n)

 

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

        for s in strs:
            count = [0] * 26

            for c in s:
                count[ord(c) - ord("a")] += 1
            ans[tuple(count)].append(s)
        
        return ans.values()