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. For each string, we create a counter. Using a dictionary counter -> group (list), we iterate through all the counters and add the string to the group. Normally, we would use a dictionary but dictonaries are not hashable. Instead, we take advantage of the fact that the string only contains lowercase letters, meaning we can use a length 26 tuple as the counter.

Code

from collections import defaultdict


def groupAnagrams(strs: list[str]) -> list[list[str]]:
    counters = []
    for s in strs:
        counter = [0] * 26
        for char in s:
            counter[ord(char) - ord("a")] += 1

        counters.append((s, counter))

    groups = defaultdict(list)
    for s, counter in counters:
        groups[tuple(counter)].append(s)

    return list(groups.values())

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

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

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