You are given a list of lowercase words strs. Two words are anagrams if one is a rearrangement
of the other's letters, using each letter exactly as often ("listen" and "silent").
Group the words so that each group holds words that are all anagrams of each other, and no two groups could be merged. Return the groups as a list of lists. The order of the groups, and of the words inside each group, doesn't matter.
Example 1
- Input
- strs = ["tea", "ate", "tan", "eat", "nat", "bat"]
- Output
- [["tea", "ate", "eat"], ["tan", "nat"], ["bat"]]
Example 2
- Input
- strs = ["", "b", ""]
- Output
- [["", ""], ["b"]]
Constraints
strsholds 1 to 10⁴ words.- Each word has 0 to 100 lowercase English letters.
Show the pattern
Hashing
Anagrams share a signature, such as their letters in sorted order. Grouping by signature is a hash map from signature to the words that have it.
See hashing in a visualiserShow the approach
Give every word a signature that all its anagrams share: its letters in sorted order (or a count of each of the 26 letters). Put each word into a hash map under its signature; the map's values are the groups.
Time: O(n · k log k) for n words of length up to k · Space: O(n · k)