Given an array of strings strs, group the anagrams together: two strings belong together when one is a rearrangement of the other's letters. Return the groups in any order, with the words inside each group in any order. Every input string appears in exactly one group.
Examples
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["ate","eat","tea"],["bat"],["nat","tan"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Example 4:
Input: strs = ["ab","ba","abc"]
Output: [["ab","ba"],["abc"]]
Constraints
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
Strings consist of lowercase English letters.
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Sorted Word as the Key Optimal
Intuition
Anagrams share exactly one thing: their letters. Sorting a word produces a canonical form that every one of its anagrams also produces, so the sorted word is a key that groups them without comparing any pair.
Algorithm
1. For each word, sort its letters to build a key. 2. Append the original word to the bucket for that key. 3. Return the buckets: the map's values. The groups, and the words inside a group, are accepted in any order.
Time & Space
Time O(n k log k) for n words of length k. Space O(n k) for the groups.