Leetcode 49: Group Anagrams

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Code

from collections import defaultdict

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = defaultdict(list)
        for s in strs:
            # you can also use tuple(sorted(s)) as dictionary key
            ss = ''.join(sorted(s))
            res[ss].append(s)
            
        return res.values()

Idea

Sort every string. Therefore, anagrams will always result in the same sorted string. Using the sorted string as key in dictionary so all anagrams will be grouped under the same key.

The time complexity is O(N MlogM), where $latex N$ is the length of strs and $latex M$ is the maximum length of single string in strs .  

Another idea is to hash every string such that a anagram group can be hashed into the same value. One way is to use prime numbers: https://discuss.leetcode.com/topic/12509/o-m-n-algorithm-using-hash-without-sort. However, this method may incur overflow.