Group Anagrams
Group Anagrams is a medium Arrays & Hashing problem from the Blind 75. The key pattern is canonical key, and a good solution runs in O(n · k log k) time.
Problem
Group strings that share the same multiset of characters. Sort strings inside each group and groups by their first item.
Examples
Example 1
Input
["tea","bat","eat","tab","ate"]Output
[["ate","eat","tea"],["bat","tab"]]Example 2
Input
["a"]Output
[["a"]]Example 3
Input
["listen","silent","enlist","google","gogole"]Output
[["enlist","listen","silent"],["gogole","google"]]Approach
Give every string a key that ignores letter order, such as its sorted letters or a 26-count signature, and bucket strings by key. Then sort inside each group and order the groups by their first string.
| Pattern | Canonical key |
|---|---|
| Time | O(n · k log k) |
| Space | O(n · k) |
Watch out for
The empty string is a valid key; several empty strings form one group.