AI Hints
Home›DSA in Python Tutorial›Anagrams and Review
DSA in Python · Lesson 29 of 132

Practice: Group Anagrams

A key for each family.

⏱ 2 min read▶ Video at 33:12🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Given a list of words, put the anagrams together. Eat, tea, and ate belong in one group. Tan and nat in another. Pause. What could you use as a dictionary key, that's the same for every word in a family?

Practice: Group Anagrams
From the video: Practice: Group Anagrams
  • Put anagrams together
  • eat, tea, ate
  • What key do they share?

Sorted letters as the key

Every word in a family has the same letters when sorted. Eat, tea, and ate all become AET. So we use the sorted letters, joined into a string, as the key. Default dict collects the words for each key. Run it. Three families, found in one pass.

group.pypython
from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
Output
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Choosing a good key

This is a powerful idea. When you need to group things, design a key that's identical for everything that belongs together. Sorted letters for anagrams. The first letter for an index. A rounded number for buckets of similar values. Then a dictionary does all the work.

keyvalue
Anagramssorted letters
Indexfirst letter
Similar valuesa rounded number
Thena dict of lists

Summary

Group anagrams by a shared key, the sorted letters, and let a dictionary collect each family. Next, a quick quiz on hashing.

Key takeaways
  • Design a shared key
  • defaultdict(list)
  • One pass
Next up: Hashing Quiz — test yourself