1. Group a list of words into anagrams.
Words are anagrams if they have the same letters, so use a key that is identical for all of them, such as the sorted word or a count of each letter.
Store groups in a hash map from key to list of words.
Sorting each word gives O(n × k log k); a 26-letter count key gives O(n × k).
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())
# group_anagrams(["eat", "tea", "tan", "ate", "nat"])
# -> [["eat", "tea", "ate"], ["tan", "nat"]]