[Leetcode 49] 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.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

 

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        # length of word = m (각 워드별로 다를 수 있겠지만..), 0 <= m <= 100
        # count of word = n, 1 <= n <= 10**4
        mem = defaultdict()
        for word in strs: # O(n)
            sorted_word = "".join(sorted(word)) # O(mlogm + m)
            if sorted_word not in mem: # O(1)
                mem[sorted_word] = []
            mem[sorted_word].append(word)
        return mem.values() # O(mem의 key 개수)

 

Runtime: 88 ms, faster than 88.39% of Python online submissions for Group Anagrams.

Memory Usage: 17.5 MB, less than 77.09% of Python online submissions for Group Anagrams.

 

java로 짰을 생각하니까 좀 아찔한데..

string은 python으로 푸는게 이득이란 말이,,, 실감이 된다,,

 

 

참고 사이트

https://www.reddit.com/r/Python/comments/54rsep/quick_tip_o1_vs_on_dictionary_in_search/

Quick Tip: O(1) vs O(N) dictionary `in` search