49. Group Anagrams

MediumLeetCode

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 <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

How to solve the problem

• HashMap

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anaDict = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            anaDict[key].append(s)
        return list(anaDict.values())

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anaDict = {}
        for s in strs:
            key = ''.join(sorted(s))
            if key not in anaDict:
                anaDict[key] = []
            anaDict[key].append(s)
        return list(anaDict.values())

Complexity

• HashMap: Time complexity: O(n * m * log(m)), Space complexity: O(n * m)
  • Where n is the number of strings and m is the average length of strings
  • The log(m) factor comes from sorting each string