[LeetCode] 49. Group Anagrams

문제 링크 

https://leetcode.com/problems/group-anagrams/description/

Intuition

• 동일한 길이를 가지고 동일한 문자열 구성을 가져야 하는 anagram! 
  
  • 그럼 저번에 문제 풀이 했을 때 처럼 set을 사용해서 풀어볼까? 
  • 그런데 이 전 문제와 다르게 grouping 해야하는 문제니까 hash 를 써야할듯 

Approach

• 단어가 3글자라고 주어진 input에서 3개 묶음의 단어가 다 있으리라고는 보장 X 
  • 있는 element를 기준으로 hash에 저장해서 확인해야함 
  • python에서 hash는? → dictionary! 
• dict의 key 값은 정렬한 값으로 저장 → 모든 element가 정렬된 값을 기준으로 hasKey() operation을 해야하므로 
• values() 는 strs의 element 리스트 
• 각 strs의 element를 확인하고, sorted 된 결과값의
  • key가 존재한다면 → 해당 values 에 추가 
  • 없다면 → 새로운 group 추가 

Complexity

Time complexity:

• O(NlogN) 

Space complexity:

Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # create a dictionary for anagrams
        # sort word and check if that word exist in a set (anagram dictionary)
        # if yes, add, if not pass 

        anagrams = dict()
        for str in strs: 
            word = "".join(sorted(str))
            # if empty 
            if not anagrams: 
                anagrams[word] = [str]
            else: 
                if word in anagrams: 
                    anagrams[word].append(str)
                else: 
                    anagrams[word] = [str]
        
        return anagrams.values()

python 초보의 사소한 실수: sorted(string) 하면 그대로 정렬된 string 값을 내어주는줄 알았다..array가 return 값일줄은..!