[leetcode] Group Anagrams

Group Anagrams

처음에 생각한 접근법

["ate","eat","tea"] 이걸 보고 set(list("ate"))처럼 문자의 종류를 가지고 anagram을 묶어야겠다고 생각했다. 하지만 이렇게 되면 bbac와 baac가 같은 종류로 묶여서 틀린다. set 같은 리스트 형태를 어떻게 key로 저장할 수 있을지 고민했지만, dict에 들어가는 key는 int나 string처럼 단일값만 들어갈 수 있을 거라 생각했다.

다른 사람 풀이

1. dict의 key로는 list는 들어갈 수 없지만 tuple은 된다. 변하지 않는 값은 들어갈 수 있다.
2. 또 새롭게 배운 것은 defaultdict(초깃값 타입)이다. 이것을 사용하게 되면 dict에 key가 없을 때 에러가 나는 게 아니라 초깃값 타입의 값으로 초기화가 된다.

res = dict()
print(res[1]) # KeyError: 1

res = defaultdict(list)
print(res[1]) # []

코드

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

리스트의 길이를 m, 단어 하나의 길이를 n이라고 했을 때 O(mn)이다.

참고 자료

• NeetCode
• defaultdict
• dict key tuple