How do you group a list of strings into groups of anagrams?
You build a signature out of each word, and you use the signature as the key in a dictionary.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
groups[signature(word)].append(word)
return list(groups.values())
So how does it work? Two words are anagrams when their letters are the same, so if you put the letters in a fixed order then two anagram words produce exactly the same string. That string is the signature, and the dictionary puts every word with the same signature into the same list.
And the complexity is O of n times k log k for the time, where n is the number of words and k is the length of the longest one, because each word has to be sorted. The space is O of n for the dictionary and the lists.
The next question in this topic looks at the signature on its own.