Group Anagrams

Group Anagrams

[문제]
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.

[입력 조건]
1 <= strs.length <= 10000 -> log2n이하?
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

[내 풀이]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = []
        while strs:  
            string = strs.pop(0)  
            cursor_len = len(string)
            target_list = [s for s in strs if len(s) == cursor_len]
            temp_list = [string] 
            for target in target_list:
                if self.checkAnagram(string, target):
                    temp_list.append(target)
                    strs.remove(target)
            result.append(temp_list)
        return result

    def checkAnagram(self,str1, str2):
        return sorted(str1)==sorted(str2)
        

해결 방법

메모리 특화 풀이

효율적이진 않은 4402ms의 시간으로 풀게 되었다. remove 함수를 지양하라고 조언을 받았다.
해설을 살펴보니 아래와 같이 주어진 문자열을 하나씩 순회하면서 각 문자열을 정렬한 후, 정렬된 문자열을 키(key)로 하여 딕셔너리에 저장하는 방식이 존재했다.
sorted를 적용하면 리스트 안이 어떻게 될 지 한 번 상상해봤으면 좋았겠다.

from collections import defaultdict

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

[출처]
https://leetcode.com/problems/group-anagrams/