Group Anagrams

Group the strings that are anagrams of each other. The groups can be returned in any order.

A way to picture it

A mail room gets letters addressed in scrambled handwriting. The trick: alphabetise the letters of each address. "eat", "tea" and "ate" all become "aet" — the same pigeonhole.

How to approach it

Give every word a key that all its anagrams share (its sorted letters). Group words by key in a hash map.

Example

Input: {"strs":["eat","tea","tan","ate","nat","bat"]}. Output: [["eat","tea","ate"],["tan","nat"],["bat"]].

Complexity: O(n · k log k) time and O(n · k) space. n words of length k, each sorted once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.