Group Anagrams Together
Problem
Group a list of words so that words using exactly the same letters, in any order, land in the same group. Return the groups with each group's words sorted, and the groups themselves sorted.
Examples
Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
Why: eat, tea and ate all use a, e and tInput: words = ["ab", "ba", "abc"]
Output: [["ab", "ba"], ["abc"]]
Why: length alone separates the second groupInput: words = [""]
Output: [[""]]
Why: edge case, the empty word forms its own groupHints
0 / 3
Comparing every word against every other is quadratic. Instead, find something you can compute from a single word that is identical for all its anagrams.
Two words are anagrams exactly when their letter multisets match, so any faithful encoding of that multiset works as a group label.
Sort each word's letters to get a canonical label, then bucket the original words under that label in a hash map. One pass builds every group.
Solution
The trick is a canonical form: a value derived from a word that is identical for every anagram of it and different for everything else. Sorting a word's letters is the simplest such form, and it doubles as a hash-map key, so one pass over the words builds all the groups. For n words of length up to k, the cost is O(n · k log k) — dominated by sorting the letters, not by comparing words to each other. A count-of-26 tuple replaces the inner sort with O(k) when the alphabet is fixed.
def group_anagrams(words):
groups = {}
for w in words:
key = "".join(sorted(w)) # same letters -> same key
groups.setdefault(key, []).append(w)
return sorted(sorted(g) for g in groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# -> [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]
print(group_anagrams(["ab", "ba", "abc"])) # -> [['ab', 'ba'], ['abc']]
print(group_anagrams([""])) # -> [['']]Stuck on the idea rather than the code? Group Anagrams covers it.