Group Anagrams
The key idea
Two words are anagrams exactly when their letters, sorted, are identical. So the sorted string is a canonical signature: bucket every word under its sorted signature in a hash map and each bucket is one anagram group.
Problem
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once. Two words belong in the same group when one is an anagram of the other.
Return a list of groups, where each group is a list of the words from strs that are anagrams of one another.
Constraints
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]consists of lowercase English letters
Examples
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Input: strs = [""]
Output: [[""]]
Input: strs = ["a"]
Output: [["a"]]
Complexity
Time: O(n*k log k) Space: O(n*k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM