[DSA][Array & Hashing] 04. Group Anagrams

LeetCode 49

 

04. Group Anagrams

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

 

 

[질문하기]

- 배열의 길이와 문자열의 길이는 최대 몇인가요?

- 그룹 간의 출력 순서도 고려해야 하나요?

- 배열의 문자열에 소문자/대문자가 혼합될 수 있나요? 알파벳이 아닌 문자가 포함될 수 있나요?

 

 

[아이디어]

Counter를 hashMap의 key로 사용해 버리자

 

 

[풀이 1] Hash with Sorting

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashMap = defaultdict(list)
        for word in strs:
            key = ''.join(sorted(word))
            hashMap[key].append(word)
        return list(hashMap.values())

Valid Anagram이라면 정렬했을 때 같은 문자열이 된다.

문제 조건에서 배열의 크기는 최대 10^4이지만 문자열의 크기는 최대 100이기 때문에 매 loop에서 배열의 원소끼리 같은 anagram인지를 비교하는 것보다 문자열을 정렬하는 것이 훨씬 효율적이다.

 

⏱️ 시간복잡도

배열을 한 번 순회하면서 문자열을 정렬하기 때문에 시간 복잡도는 O(nklogk)이다.

🧠 공간복잡도

배열의 원소 개수만큼의 공간이 필요하고, 문자열을 정렬할 때 O(k)의 공간을 필요로 하기 때문에 공간 복잡도는 O(nk)이다.

 

 

[풀이 2] Hash with Counter

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s)
        return list(res.values())

 

⏱️ 시간복잡도

배열을 한 번 순회하면서 Counter를 만드는데, Counter는 문자열 k만큼 반복되므로 시간 복잡도는 O(nk)이다.

🧠 공간복잡도

배열의 원소 개수 x 문자열의 개수만큼의 공간이 필요하므로 공간 복잡도는 O(nk)이다.