Group Anagrams

Problem

Given a list of lowercase words strs, partition them into groups such that every word in a group is an anagram of every other word in the same group. Two words are anagrams when one can be rearranged into the other, using every letter exactly once. Return the groups as a list of lists; the order of groups and the order of words within a group do not matter.

• The list is non-empty and holds at most 25,000 words.
• A word may be empty; no word is longer than 120 letters.
• Only lowercase ASCII letters appear (the 26-slot count key depends on this).

Examples

• strs = ["listen", "silent", "enlist", "below", "elbow", "cat"] → [["listen","silent","enlist"], ["below","elbow"], ["cat"]]. Three distinct multisets of letters.
• strs = ["", "x", ""] → [["", ""], ["x"]]. Two empty words are anagrams of each other.
• strs = ["zzz"] → [["zzz"]]. One word forms one group.

Hints

1. Two words are anagrams exactly when some property of them is identical. What property?
2. If you could compute a single value that is the same for all anagrams and different otherwise, grouping would be a one-pass hash-map fill.
3. Use the sorted word, or a 26-slot letter count, as the dictionary key.