Leetcode Python - 49. Group Anagrams

Leetcode #49 - Group Anagrams

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 49 ‘Group Anagrams’을 파이썬으로 풀어 보도록 하겠습니다.

list에서 anagrams(철자 순서만 다른 단어)들 끼리 묶어 반환하는 문제입니다.

discuss 참고, 포인트는 해당 단어들을 sort해 tuple로 변환해 dictionary에 key로 두고 일치할 때마다 list를 append 해주는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def groupAnagrams(self, strs):
        d = {}
        
        for w in strs:
            key = tuple(sorted(w))
            d[key] = d.get(key,[]) + [w]
            
        return d.values()

시간복잡도는

• O(n) : 한 번의 loop

공간복잡도는

• O(n) : strs를 dictionary에 append