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

Solution

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
from typing import List


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__approach_1 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 | Time: \(O(nkg)\) — compare each string to groups | Auxiliary Space: \(O(kg)\) — store frequency dictionary for each group

group_anagrams__approach_1.groupAnagrams(strs: List[str]) → List[List[str]]

Group strs into anagrams.