visual walkthrough
Group Anagrams
Choosing a good hash key (sorted string or count tuple) is the whole problem.
The idea
Anagrams are the same letters in a different order, so sorting the letters gives every member of a family the same "fingerprint". Use that fingerprint as a key in a hash map and the groups assemble themselves.
Comparing every pair of words works too, but repeats a lot of work.
Complexity
| approach | time | space |
|---|---|---|
| Compare words | O(n² · k log k) | O(n) |
| Sorted-letters key | O(n · k log k) | O(n) |