[LeetCode] 49. Group Anagrams

49. Group Anagrams

Medium

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 lowercase English letters.

---

문제 풀이

• 단어 리스트가 주어진다. 
• 아나그램을 찾는 것이 목표이다. 
• 아나그램이란, 단어를 구성한 알파벳과 알파벳의 갯수가 같아야한다.
• 제한 조건은 최대 10^4이기 때문에 O(N^2) 알고리즘으로 푸는게 가능하다.

Sorted word

• 딕셔너리 리스트를 만든다. 
• 각 단어를 정렬해서 정렬된 단어를 키값으로 저장한다. 
• 그리고 딕셔너리의 값을 정답 리스트에 저장하여 반환한다.
• 시간복잡도는 O(N * KlogK)이다. 단어를 검색하는데 N이 걸리고 KlogK는 각 단어의 정렬 시간복잡도이다.

Count

• 해쉬 테이블을 사용하여 각 단어의 알파벳 갯수를 저장한다. 
• 알파벳의 갯수를 저장하는 배열은 26개로 a~z이다. 
• 그리고 저장된 배열을 tuple로 딕셔너리에 key값으로 저장하고 단어들을 배열에 추가해준다.
• 그리고 딕셔너리의 값(배열)을 반환한다.
• 시간복잡도는 O(N * K)이다. 각 단어를 탐색하는 시간 N 과 각 단어의 알파벳의 갯수를 세는 K시간이 걸린다. 

소스 코드

Sorted word

# dict list sorted O(N KlogK)
        d = defaultdict(list)
        for word in strs:
            t = ''.join(sorted(word))
            d[t].append(word)
        res = [l for l in d.values()]
        return res

Count Dictionary

# count
        d = defaultdict(list)
        for word in strs:
            count = [0] * 26
            for c in word:
                count[ord(c) - ord('a')] += 1
            d[tuple(count)].append(word)
        return d.values()