Given an array of strings, group anagrams together.

Example:

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

Output:

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

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Solution

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = defaultdict(list)

        for aStr in strs:
            hashmap[str(sorted(aStr))].append(aStr)

        return list(hashmap.values())

Test Cases

test = Solution()
answer = test.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert answer == [
  ["eat","tea","ate"],
  ["tan","nat"],
  ["bat"]
], answer
print('All Passed!')

Big O Analysis

Space Complexity: O(NK)

Time Complexity: O(NK log K) where N is the length of the input array and K is the max length of words in the array