Group the anagrams
Write group_anagrams(words) that groups words which are anagrams of each other. Return a list of groups; the order does not matter.
group_anagrams(["eat", "tea", "tan", "ate", "nat"])
# [["eat", "tea", "ate"], ["tan", "nat"]]Show hint
Anagrams look identical once their letters are sorted. Use that as a dictionary key.
Show solution
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w)
return list(groups.values())Sorting the letters gives every anagram the same "signature", and the dictionary collects words by signature. For n words of length up to k, this is O(n · k log k).
Want a problem like this every day? See today's problem and keep a streak going.