LC 49 - Group Anagrams

Question

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

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

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

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.

Links

Question here and solution here

Solution

concept

The most basic way to solve is notice that we can sort the word (by char) and anagrams will have the same sorted char. But sorting is $O(n\log n)$ and if we have m words then the overall time complexity is $m \cdot n \log n$.

code

class Solution(object):
    def groupAnagrams(self, strs):
        """
		with sorting
        time complexity = O(n * mlogm) where n is the number of strings and m is the length of the longest string
        """
        hash_map = {}

        for _str in strs:
            sorted_str = "".join(sorted(_str))
            if sorted_str not in hash_map:
                hash_map[sorted_str] = [_str]
            else:
                hash_map[sorted_str].append(_str)
                
        return hash_map.values()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
		without sorting
        time complexity = O(n * m) where n is the number of strings and m is the length of the longest string
        """
        res = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            res[tuple(count)].append(s)
        return list(res.values())

Complexity

time: $O(m \cdot n)$
space: $O(m \cdot n)$