Group anagrams

Question

Given a list of strings, group together all strings that are anagrams of each other (identical letters, any order).

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
-> [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Return the groups (any order within and across groups). Aim for better than the $O(n^2)$ all-pairs comparison.

Accepted Answer

The trick is to map each word to a canonical form that is identical exactly for anagrams, then bucket by that key in a hash map. The simplest canonical form is the sorted string: "eat", "tea", and "ate" all become "aet". On the example, keys are aet, aet, ant, aet, ant, abt, producing the three groups shown. With n words of length up to L, sorting each key costs O(n \, L \log L) total. To shave the log factor, use a letter-count signature instead, a tuple of 26 counts, giving O(nL): A tuple (immutable, hashable) is required here, a list can't be a dict key. Avoid "clever" keys like summing ch…

Group anagrams

Your answer

More Coding questions