Group Anagrams

medium LeetCode #49
array hash-table string sorting

Description

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, using all the original letters exactly once.

Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation: The strings "eat", "tea", and "ate" are anagrams (all contain letters a, e, t). The strings "tan" and "nat" are anagrams (both contain a, n, t). The string "bat" has no anagram in the list.

Example 2:
Input: strs = [""]
Output: [[""]]
Explanation: The empty string is its own anagram group.

Example 3:
Input: strs = ["a"]
Output: [["a"]]
Explanation: A single character string forms its own group.

Constraints

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

Complexity

Show Complexity
  • Time: O(n * k log k)
  • Space: O(n * k)

Hints

Show Hints
Pattern
Hash map with sorted string as key
Approach
For each string, sort its characters to get a key. Use a hash map where key is the sorted string and value is a list of original strings that share that sorted form.
Complexity
Sort each string to create canonical form, group by canonical form

Solutions

Show PY Solution 
from collections import defaultdict


def solution(strs: list[str]) -> list[list[str]]:
    m = defaultdict(list)

    for s in strs:
        ss = "".join(sorted(s))
        m[ss].append(s)

    return list(m.values())