[LeetCode > Medium > 49] Group Anagrams

문제

• https://leetcode.com/problems/group-anagrams/description/
• Runtime: 71ms, Memory 19.80MB
• 애너그램이 같은 문자열끼리 묶은 이중 리스트를 반환

내 풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    	# 정렬한 애너그램이 key, 해당 애너그램인 문자열 리스트가 value
        results = dict()
        
        for s in strs:
            # 문자열을 정렬해 key를 구한다.
            sorted_s = list(s)
            sorted_s.sort()
            key = ''.join(sorted_s)
            
            # key가 이미 존재하는 경우
            if key in results:
                results[key].append(s)
            # key가 없다면, 값 새로 생성
            else:
                results[key] = [s]
        return results.values()

• 시간 복잡도
  • strs의 길이를 n, 각 str의 길이를 k라고 하면, O(n²)
  • 1 <= n <= 10⁴, 1 <= k <= 100
  • ( for문에서 n ) * ( sort에서 k + in에서 최대 n-1 )