loading

49. Group Anagrams — Step-by-Step Visualization

mediumLeetCode #49ArrayHash TableStringSorting

Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. **Example 1:** Input: `strs = ["eat","tea","tan","ate","nat","bat"]` Output: `[["bat"],["nat","tan"],["ate","eat","tea"]]` **Example 2:** Input: `strs = [""]` Output: `[[""]]` **Example 3:** Input: `strs = ["a"]` Output: `[["a"]]`

Algorithm Pattern

Hash Map / Canonical Key

Key Idea

Two strings are anagrams if they have the same characters in the same frequencies. We can create a 'canonical key' for each string (either by sorting its letters or by counting character frequencies) and use this key to group the strings in a hash map.

Step-by-Step Approach

  1. Initialize an empty hash map (e.g. `ans = {}`) to store groups.
  2. For each string `s` in the input array:
  3. 1. Generate a canonical key. The easiest way is to sort the string: `key = ''.join(sorted(s))`.
  4. 2. If the key is not in the hash map, create an empty list for it.
  5. 3. Append the original string `s` to the list corresponding to that key.
  6. Finally, return all the values (the lists of grouped anagrams) from the hash map.

Common Gotchas

  • Make sure you use the *original* string for the grouping, not the sorted one.
  • Empty strings are valid and should be grouped together.

Related Problems

← All problems