Two words are anagrams if one is a rearrangement of the other's letters. Write group_anagrams(words) that splits words into groups of mutual anagrams and returns a list of those groups.
1 <= len(words) <= 10^4; each word has 0 to 100 lowercase letters.- Every input word (including duplicates) lands in exactly one group. The groups can be in any order, and the words inside a group can be in any order.
Comparing each word against every group is O(n²) comparisons. Aim for about O(n · L log L) or better, where L is the word length.
group_anagrams(["pots", "tops", "cat", "stop", "act", "dog"])
# [["pots", "tops", "stop"], ["cat", "act"], ["dog"]] in some order
group_anagrams([""]) # [[""]]
Show hint
find something you can compute from a single word that is identical for all of its anagrams and different for everything else, then use it as a dictionary key.