Group Anagrams

def groupAnagrams(strs):
    groups = {}                    # key -> list of words
    for word in strs:
        key = ''.join(sorted(word))    # 'tea' -> 'aet'
        groups.setdefault(key, []).append(word)
    return list(groups.values())

Group Anagrams. Given a list of words, group together the anagrams: words made of exactly the same letters, in any order.

Take eat, tea, tan, ate, nat and bat. Eat, tea and ate share one group. Tan and nat make another. Bat is all alone.

The naive way compares every pair of words, checking whether their letters match. Six words already make fifteen pairs, and the pairs grow with the square of the list.

Instead, give each word a label that all its anagrams share. Sort its letters: eat, tea and ate all become A, E, T. That sorted word is the key. A count of each of the twenty six letters works as a key too.

In code, keep a hash map from each key to a list of words. For each word, sort its letters to build the key, then append the word to that key's list. At the end, return the map's values.

Let's sort the mail. Eat becomes A, E, T: a new slot. Tea has the same key, so the same slot. Tan becomes A, N, T: a second slot. Ate joins the first, nat joins the second, and bat opens a third slot, A, B, T. Three groups, in one pass.

Each of the n words is sorted once, in k log k time for k letters, so the time is n times k log k. The map holds every letter once, so the space is n times k.

Sort the letters, find the slot, drop it in. That's Group Anagrams.