Free Hashing lessonsHashing · Stage 1 · Grouping by key · Step 1

Same key, same group

Group words by a key that's equal for all rearrangements. About 9 minutes.

Find a label that equal things share

A library groups books by subject so similar ones sit together. To group words that are anagrams of each other, you need a label that all anagrams share and no other word does.

Sort the letters of each word. "eat", "tea" and "ate" all become "aet". That sorted word is the label: the key.

The key: the word's letters, sorted.

words = [eat, tea, tan, ate, nat, bat]

eat

tea

tan

ate

nat

bat

word

key: "aet"
groups: {aet}

Sort the letters of "eat": the key is "aet". Put it in the set.

Move 1 of 5

The map does the grouping

Put each word's key into a set (to count the groups) or into a map from key to a list of words (to collect them). Words with the same key land in the same place automatically. You never compare two words directly.

A good key is equal exactly when two things belong together. That idea, "find the right key", comes up again and again.

Same key: same group, automatically.

In code

groups = set()
for w in words:
    groups.add("".join(sorted(w)))
return len(groups)

Quick check

Which words share a key with "listen"?

A"silent" and "enlist"
B"list"
CNone

Show the answer

"silent" and "enlist". All three sort to "eilnst".

Your problem

How many anagram groups?

You get a list of lowercase words. Words that are rearrangements of each other belong to the same group. Return how many groups there are.

Example

words = ["eat", "tea", "tan", "ate", "nat", "bat"] → 3

0 ≤ words ≤ 10,000 · 0 ≤ each length ≤ 100 · only a to z

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.