Anagram Clusters
MediumTries & Strings
Problem
A word-game server wants to group words that use exactly the same letters. Given a list words, split it into clusters where two words are in the same cluster if and only if one is a rearrangement of the other.
Return the clusters; the order of clusters and of words inside a cluster does not matter. Repeated words stay repeated.
Example 1
- Input:
- words = ["listen","silent","enlist","google","gogole","cat","act","tac","dog"]
- Output:
- [["listen","silent","enlist"],["google","gogole"],["cat","act","tac"],["dog"]]
Each cluster shares the same letter counts.
Example 2
- Input:
- words = [""]
- Output:
- [[""]]
Constraints
- 1 ≤ words.length ≤ 10^4
- 0 ≤ words[i].length ≤ 100
- Lowercase English letters only.
Hint
Show the first hint
Two words belong together when something about them is identical. What?
Walkthrough
How to approach it
01Clarify before coding
- Does the output order matter? No, neither for clusters nor inside them.
- Can words repeat? Yes, duplicates go in the same cluster and are kept.
- Can a word be empty? Yes; all empty words form one cluster.
02Brute force
Compare every pair of words with a rearrangement check and union the matches.
Cost: O(n²·k) for n words of length k: 10^8 pairs times the per-pair check.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.