Group Anagrams (LeetCode 49)

The problem

You get a list of strings strs. Group together the words that are anagrams of each other (same letters, same counts, any order). Return the groups in any order.

Input:  ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

eat, tea and ate all use one a, one e and one t. tan and nat share their letters. bat has no partner.

How to think about it

Start with brute force. For each word, compare it with every other word using an anagram check, and union the matches into groups. With n words of length k, that’s O(n² · k) comparisons, and the grouping bookkeeping is fiddly.

The key insight: give every word a canonical form that only anagrams share. If two words are anagrams, sorting their letters gives the same string: "eat", "tea" and "ate" all sort to "aet". Words that aren’t anagrams sort to different strings. So the sorted letters act as a fingerprint for the group.

Then let a dictionary do the grouping. Use the fingerprint as a dictionary key and append each word to the list stored under its key. One pass over the words builds every group at once. A defaultdict(list) means you never have to check whether a key exists yet.

Which pattern is this? Hash map grouping by a canonical key. The tell is “group items that are equivalent under some rearrangement”.

Approach

1. Create groups, a defaultdict(list).
2. For each word s, compute key = tuple(sorted(s)). A tuple is used because lists can’t be dictionary keys.
3. Append s to groups[key].
4. Return all the lists in groups.

Solution

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s)); groups[key].append(s)   # anagrams share the sorted key
    return list(groups.values())
# group_anagrams(["eat","tea","tan","ate","nat","bat"])
#   -> [["eat","tea","ate"],["tan","nat"],["bat"]]

Dry run

On the example (keys shown as joined strings for readability):

The result is [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]], in the order the keys first appeared.

Complexity

• Time: O(n · k log k) for n words of maximum length k: sorting each word costs O(k log k), and the dictionary work is O(k) per word to hash the key.
• Space: O(n · k). Every word is stored once in the groups, plus one key per group.

Edge cases and pitfalls

• Empty string: [""] gives [[""]]. The key is the empty tuple, which is valid.
• Empty list: returns [].
• Using a list as the key raises TypeError: unhashable type. Use a tuple or "".join(sorted(s)).
• Faster key for long words: count the 26 letters and use the counts tuple as the key. That’s O(n · k) instead of O(n · k log k).
• Duplicate words (["a", "a"]) both go into the same group, which is what’s expected.

Related problems

• Valid Anagram (LeetCode 242): the pairwise check this generalises.
• Isomorphic Strings (LeetCode 205): a different notion of “same shape” between strings.
• Top K Frequent Elements (LeetCode 347): another “bucket with a dictionary, then read the buckets” problem.