Group Anagrams

Problem

https://leetcode.com/problems/group-anagrams/

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:sup:`4`

• 0 <= strs[i].length <= 100

• strs[i] consists of lowercase English letters.

Pattern

Array, Hash Table, String, Sorting

Approaches

Character Count

Explanation

We can check whether 2 strings are anagrams by counting the number of each letter in a dictionary. If the 2 strings are anagrams, then the dictionaries will be equal. For each string, check whether it is an anagram of any of the existing groups. If so, add it to that group. Otherwise, create a new group. To save time on dictionary creation, we store a dictionary for each group.

Code

from collections import Counter


def groupAnagrams(strs: list[str]) -> list[list[str]]:
    """Group ``strs`` into anagrams."""
    dicts = []
    groups = []
    for s in strs:
        d = Counter(s)

        for i, group in enumerate(groups):
            if d == dicts[i]:
                groups[i].append(s)
                break
        else:
            groups.append([s])
            dicts.append(d)

    return groups

Test

>>> from group_anagrams__character_count import groupAnagrams
>>> groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
>>> groupAnagrams([""])
[['']]
>>> groupAnagrams(["a"])
[['a']]

Complexity

\(n\) is the number of strings in the input array, \(k\) is the maximum length of a string in the input array, and \(g\) is the number of groups

Measure	Complexity	Notes
Time	\(O(nkg)\)	compare each string to groups
Auxiliary Space	\(O(kg)\)	store frequency dictionary for each group

group_anagrams__character_count.groupAnagrams(strs: list[str]) → list[list[str]]

Group strs into anagrams.