Coding Puzzle: Anagram Groups

• Difficulty: Medium

Problem Definition

Given a list of strings, group the list into sets of words that are anagrams of each other.

Assume that you already have a function that checks if two strings are anagrams and that it has a space complexity $O(n)$ and a runtime complexity $O(n)$, where $n$ is the length of the larger of the two words. You can also find an implementation of such a function in Anagram Check.

Examples

Some test cases to verify our solution.

inp = ["tea", "ate", "eat", "bat", "eta", "tab", "rot", "hit"]
expected = [{"tea", "ate", "eat", "eta"}, {"tab", "bat"}, {"rot"}, {"hit"}]
result = anagram_groups(inp)
for exp in expected:
    assert exp in result

inp = ["tea", "bat", "rot", "hit"]
expected = [{"tea"}, {"bat"}, {"rot"}, {"hit"}]
result = anagram_groups(inp)
for exp in expected:
    assert exp in result

Solution

from collections import defaultdict

def anagram_groups(arr):
    processed = set()
    groups = defaultdict()
    n = len(arr)
    for i in range(n):
        item_1 = arr[i]
        if item_1 not in processed:
            processed.add(item_1)
            groups[item_1].add(item_1)
            for j in range(i, n):
                item_2 = arr[j]
                if item_2 not in processed and are_anagrams(item_1, item_2):
                    processed.add(item_2)
                    groups[item_1].add(item_2)
    return [list(groups[leader]) for leader in groups]

Complexity

Let $n = $ len(arr), $m = $ max(len(x) for x in arr).

Runtime complexity should be $O(n^2 \cdot m)$.

Auxiliary space complexity should be $O(n \cdot m)$.