LeetCode - 49. Group Anagrams

[LeetCode] 49. Group Anagrams

LeetCode 49번 문제를 풀어보았다.. Link

Problem

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.

Intuition

이전 Valid anagram 문제와 비슷하게 Dictionary를 활용하여 푸는 Hashing 문제 중 하나이다.

다만 다른것은 그저 서로 Anagram인지 아닌지 판별하는 것이 아니라, Anagram인 것들 끼리 찾아서 묶어야 한다는 점이다.

Valida anagram 문제에서는 Dictionary의 같음을 기준으로 Anagram인지 아닌지 판별하였으니까, Dictionary를 Key값으로 하여 Anagram끼리 묶을수 있을 거라고 생각했다.

Approach

하지만 Dictionary는 다른 Dictionary의 Key가 될 수 없다는 에러가 뜨면서 어쩔수 없이 나는 또다시 각 String 별 Dictionary가 같은지 같지 않은지 판별하는 괴상한 코드를 작성했다.

신기하게도 통과하긴했지만, 정석은 아니었고 코드도 매우 난잡했기에 결국 정답을 참고하였다.

Sorting을 사용하는 방법과 리스트로 Key를 만들어 활용하는 방법이 있는데, 리스트로 Key를 만들어 사용하는 방법에 대해 포스팅하도록 하겠다.

1. 빈 딕셔너리 dic을 생성
2. strs[i]는 strs의 i번째 element
3. count는 각 26개의 알파벳의 개수가 저장되는 리스트
4. c는 strs[i]의 j번째 element라고 하고 ord함수로 아스키코드로 변환하여 a부터 z까지가 0부터 25의 숫자로 변환되도록 함
5. count[ord(c) - ord(‘a’)] += 1을 j가 len(strs[i])-1일 때까지 반복함
6. dic에 count를 key 값으로하고 value인 빈 리스트에 strs[i]를 append
7. i가 len(strs)-1일 때까지 반복함
8. dic의 values를 반환한다.

Complexity

• Time complexity:

  strs의 개수를 n, strs[i]의 길이를 m이라고 할 때, O(n * m)

• Space complexity: O(n * m)

My Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
                
            if tuple(count) in dic:
                dic[tuple(count)].append(s)
            else:
                dic[tuple(count)] = [s]

        return dic.values()

Dictionary는 또다른 Dictionary의 Key값이 되지 못하지만 Tuple은 가능하다는 사실, 알고있었나요?

Dictionary를 사용하는것말고도 List를 활용하여 Anagram을 판별할수도있다는 것을 보여준 좋은 예제라고 생각한다.

내가 처음에 써서 통과했던 코드도 함께 첨부하겠다. 매우 난잡하고 비효율적이니 참고하지 말기를..

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        strs_dic = {}
        for s in strs:
            strs_dic[s] = {}
            for c in s:
                strs_dic[s][c] = strs_dic[s].get(c, 0) + 1
        
        answer = []
        seen = [False] * len(strs)
        for i in range(len(strs)):
            if not seen[i]:
                seen[i] = True
                temp = [strs[i]]
                for j in range(i+1, len(strs)):
                    if not seen[j]:
                        if strs_dic[strs[i]] == strs_dic[strs[j]]:
                            temp.append(strs[j])
                            seen[j] = True
                answer.append(temp)

        return answer