How Do You Group Anagrams?

Give every word a canonical key that is the same for all its anagrams, then use that key to bucket the words in a dictionary. The simplest canonical key is the word with its characters sorted, because sorting produces the same sequence for any two words that contain the same characters.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

The output is three groups: eat, tea and ate together, tan and nat together, and bat on its own. The key for the first group is aet, for the second ant and for the third abt, and the dictionary groups by that key.

The mechanism is that the key must be identical exactly when the words are anagrams, so the dictionary does the grouping for you. The cost is dominated by sorting each word, which is O of m log m for a word of length m, so the whole pass is O of n times m log m for n words of length m. Using a frequency tuple as the key instead makes each key O of m to build and O of m to hash, which is linear overall and is the version to prefer when the words are long.

The trade-off to name is space. You store every word plus its key, so the algorithm is linear in the total input size, and the sorted keys can be several times larger than the words themselves. If you only need to detect whether any two words are anagrams, you can hash the keys into a set and compare hashes, which uses less memory but loses the grouping. And in practice the first two words in a group are usually enough to know the group exists, so streaming with early exit is possible.

Two words are anagrams when one is a rearrangement of the other, which means they have the same length and the same multiset of characters. A signature is a value that captures that multiset, so that two words are anagrams exactly when their signatures are equal.

def signature(word):
    return "".join(sorted(word))

print(signature("listen"), signature("silent"))
print(signature("listen") == signature("silent"))
print(signature("listen") == signature("silentx"))

The first line prints eilnst twice, showing that both words produce the same signature. The next two lines print True and False, so the signature test matches the anagram relation exactly.

The mechanism is that the signature is a canonical form. Whatever order the characters arrive in, the signature comes out the same, and different character sets produce different signatures. That is the same idea as putting objects into a set and using the set itself as the key, or normalising a record before comparing it.

The trade-off to name is the cost of building the signature. The sorted version is O of m log m for a word of length m, and the tuple-of-counts version is O of m but depends on a fixed alphabet, which is why the counts version is faster for long words and the sorted version is easier to read and works for any character set. Whichever you choose, the important property is that the signature is hashable and that equal signatures mean equal anagram classes, because that is what lets you group in a single pass.