Group Anagrams

Medium · group by sorted key. Real solution for this problem — same player as the hand-authored deep-dives.

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 49. Group Anagrams. The copyrighted prompt is on LeetCode. This page is a working group by sorted key for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

—Player inputs are capped so the animation stays readable.
—Match LeetCode's own constraints when you submit there.

Examples

Input

strs =: eat tea tan ate nat bat

Output

[[eat, tea, ate], [tan, nat], [bat]]

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Sort each word as the map key

Anagrams share a sorted signature. Bucket words by sorted(word).

eat, tea, ate all sort to aet. One hash map from signature → list is the whole algorithm.

Algorithm

For each word, sort its letters to get a key.
Append the word to that key's bucket.
Return the buckets.

Time: O(n k log k)
Space: O(n k)

Solution.py

1class Solution:2    def groupAnagrams(self, words: list[str]) -> list[list[str]]:3        groups: dict[str, list[str]] = {}4        for w in words:5            key = "".join(sorted(w))6            groups.setdefault(key, []).append(w)7        return list(groups.values())

Watch this run

Interactive walkthrough

Playing “Sort each word as the map key”. Edit the input, hit Run, then scrub.

Approach: Sort each word as the map key

Loading animation…