Group Anagrams
Medium· hash map· canonical key
Problem
Given a list of words, group together the words that are anagrams of each other. The groups, and the words inside each group, may be returned in any order.
Examples
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Words sharing the same letters end up in the same group.
Constraints
- • 1 <= strs.length <= 10^4
- • 0 <= strs[i].length <= 100
- • Lowercase English letters only
Hints & approach
Hint 1
Anagrams become identical once you put them in a canonical form.
Hint 2
Use that canonical form as a hash map key.
Hint 3
Sorting each word works; a 26-count signature avoids the sort.
Approachtry the hints first
Map each word to a key that is the same for all its anagrams: either the word's letters sorted, or a tuple of 26 letter counts. Use a hash map from key to list of words, appending each word to its key's list. The map's values are the groups. The count-signature key makes each word O(k) instead of O(k log k).
Time O(n * k) with count keys · Space O(n * k)