Group Words by Anagram Signature

Interview Problem Beginner Medium Hash Map String Hashing

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.groupAnagrams(words). Return groups where two words share a group exactly when one is an anagram of the other. Group and word order do not matter.

Starter code

class Solution:
    def groupAnagrams(self, words: list[str]) -> list[list[str]]:
        pass

Test cases

multiple-groups

{
  "args": [
    [
      "eat",
      "tea",
      "tan",
      "ate",
      "nat",
      "bat"
    ]
  ]
}

Expected: [["eat","tea","ate"],["tan","nat"],["bat"]]

Wizard outline

Step 1: Initialize Solution.groupAnagrams
Replace the empty starter with the first real state owned by Solution.groupAnagrams. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Empty Word case
Complete the readable core algorithm for one representative Interview case. Choose a canonical immutable signature and accumulate words by that hash-map key.
Step 4: Harden the Signature Not Prefix boundary
Repair the reviewed boundary and pass the complete submission contract. Two words have the same sorted-character signature exactly when every character multiplicity matches, so the dictionary partitions precisely the anagram equivalence classes.

Footguns and prerequisites

A mutable list cannot be used as a dictionary key; convert the sorted characters to a tuple or string.
hashing and sets

Reviewed references

LeetCode 49 — Group Anagrams

Practice prerequisites

Count Word Frequencies(opens in a new tab)
Counting tokens into a hash map rehearses the same frequency-signature construction used to place anagrams into canonical groups.
Track Previously Seen Values(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing group anagrams as a complete Interview Problem.

Recommended approach and implementation

Sort each word's characters into an immutable signature and append the original word to that signature's list.

Why it works: Two words have the same sorted-character signature exactly when every character multiplicity matches, so the dictionary partitions precisely the anagram equivalence classes.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, words):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        groups = defaultdict(list)
        for word in words:
            signature = tuple(sorted(word))
            groups[signature].append(word)
        return list(groups.values())