Group Anagrams Using Hash Map in DSA Python - Build from Scratch

Group Anagrams Using Hash Map

📖 Scenario: You work in a bookstore. You have a list of book titles, but some titles are anagrams of each other (words made by rearranging letters). You want to group these anagrams together to organize your inventory better.

🎯 Goal: Build a program that groups a list of words into lists of anagrams using a hash map (dictionary).

📋 What You'll Learn

Create a list of words called words with the exact values: 'listen', 'silent', 'enlist', 'hello', 'olleh', 'world'

Create an empty dictionary called anagram_groups to store grouped anagrams

Use a for loop with variable word to iterate over words

Inside the loop, create a variable sorted_word that holds the sorted letters of word joined back as a string

Use sorted_word as a key in anagram_groups and append word to the list of anagrams for that key

Print the list of grouped anagrams from anagram_groups.values()

💡 Why This Matters

🌍 Real World

Grouping anagrams helps organize words or data that are similar but shuffled, useful in spell checkers, word games, and data cleaning.

💼 Career

Understanding hash maps and grouping data is important for software developers working with data processing, search engines, and text analysis.

1

Create the list of words

Create a list called words with these exact strings: 'listen', 'silent', 'enlist', 'hello', 'olleh', 'world'

DSA Python

# Create the list of words
# Your code here

Hint

Use square brackets [] to create a list and separate words with commas.

2

Create the dictionary to hold anagram groups

Create an empty dictionary called anagram_groups to store the grouped anagrams

DSA Python

words = ['listen', 'silent', 'enlist', 'hello', 'olleh', 'world']
# Create an empty dictionary called anagram_groups
# Your code here

Hint

Use curly braces {} to create an empty dictionary.

3

Group words by sorted letters

Use a for loop with variable word to iterate over words. Inside the loop, create a variable sorted_word that holds the sorted letters of word joined back as a string. Then, if sorted_word is not a key in anagram_groups, add it with an empty list. Append word to the list for sorted_word in anagram_groups.

DSA Python

words = ['listen', 'silent', 'enlist', 'hello', 'olleh', 'world']
anagram_groups = {}
# Group words by their sorted letters
# Your code here

Hint

Use sorted(word) to get letters sorted, then ''.join(...) to make a string. Use if key not in dict to check keys.

4

Print the grouped anagrams

Print the list of grouped anagrams by printing list(anagram_groups.values())

DSA Python

words = ['listen', 'silent', 'enlist', 'hello', 'olleh', 'world']
anagram_groups = {}
for word in words:
    sorted_word = ''.join(sorted(word))
    if sorted_word not in anagram_groups:
        anagram_groups[sorted_word] = []
    anagram_groups[sorted_word].append(word)
# Print the grouped anagrams
# Your code here

Hint

Use print(list(anagram_groups.values())) to show grouped anagrams as a list of lists.

Practice

1. What is the main idea behind grouping anagrams using a hash map?

easy

A. Use the first character of the string as the key

B. Use the length of the string as the key

C. Use sorted strings as keys to group words with the same letters

D. Use the last character of the string as the key

Solution

1. Step 1: Understand anagrams

   Anagrams are words with the same letters in different orders.

2. Step 2: Use sorted strings as keys

   Sorting letters of each word gives a common key for all anagrams.

3. Final Answer:

   Use sorted strings as keys to group words with the same letters -> Option C

4. Quick Check:

   Sorted string key groups anagrams = C [OK]

Hint: Sort each word to find its anagram group key [OK]

Common Mistakes:

• Using string length as key groups wrong words
• Using first or last character misses many anagrams
• Not sorting letters before using as key

2. Which of the following Python code snippets correctly initializes an empty hash map (dictionary) to group anagrams?

easy

A. anagrams = {}

B. anagrams = ()

C. anagrams = set()

D. anagrams = []

Solution

1. Step 1: Identify dictionary initialization

   In Python, an empty dictionary is created with curly braces {}.

2. Step 2: Check other options

   List uses [], set uses set(), tuple uses (). Only {} is dictionary.

3. Final Answer:

   anagrams = {} -> Option A

4. Quick Check:

   Empty dictionary = {} [OK]

Hint: Use {} to create an empty dictionary in Python [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using set() which creates a set, not a dictionary
• Using () which creates a tuple, not a dictionary

3. What is the output of the following code?

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
anagrams = {}
for word in words:
    key = ''.join(sorted(word))
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(list(anagrams.values()))

medium

A. [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

B. [['eat', 'tea'], ['tan', 'nat'], ['bat', 'ate']]

C. [['eat', 'ate'], ['tan', 'nat'], ['bat', 'tea']]

D. [['eat'], ['tea'], ['tan'], ['ate'], ['nat'], ['bat']]

Solution

1. Step 1: Sort each word and group

   Words "eat", "tea", "ate" sorted become "aet"; grouped together. "tan", "nat" sorted "ant"; grouped. "bat" sorted "abt"; alone.

2. Step 2: Collect groups in dictionary values

   Values are lists of grouped anagrams: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

3. Final Answer:

   [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] -> Option A

4. Quick Check:

   Sorted keys group words correctly = A [OK]

Hint: Sort letters, use as key, group words in list [OK]

Common Mistakes:

• Appending words to wrong keys
• Not sorting words before grouping
• Mixing groups or missing words

4. Find the error in this code that tries to group anagrams:

words = ["abc", "bca", "cab"]
anagrams = {}
for word in words:
    key = sorted(word)
    if key not in anagrams:
        anagrams[key] = []
    anagrams[key].append(word)
print(anagrams)

medium

A. The dictionary is not initialized correctly

B. The print statement syntax is wrong

C. The append method is used incorrectly

D. sorted(word) returns a list, which cannot be used as a dictionary key

Solution

1. Step 1: Check key type used in dictionary

   sorted(word) returns a list, but lists are not hashable and cannot be dictionary keys.

2. Step 2: Fix by converting list to string or tuple

   Use key = ''.join(sorted(word)) or key = tuple(sorted(word)) to make hashable key.

3. Final Answer:

   sorted(word) returns a list, which cannot be used as a dictionary key -> Option D

4. Quick Check:

   Dictionary keys must be hashable, list is not [OK]

Hint: Convert sorted list to string or tuple before using as key [OK]

Common Mistakes:

• Using list as dictionary key causes TypeError
• Not converting sorted result to string or tuple
• Ignoring error messages about unhashable types

5. Given the list words = ["listen", "silent", "enlist", "google", "gogole", "abc"], which code snippet correctly groups the anagrams and returns the groups sorted alphabetically by their first word?

hard

A. anagrams = {}
for w in words:
key = w
anagrams[key] = w
print(list(anagrams.values()))

B. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams.setdefault(key, []).append(w)
groups = list(anagrams.values())
groups.sort(key=lambda x: x[0])
print(groups)

C. anagrams = {}
for w in words:
key = ''.join(sorted(w))
anagrams[key] = w
print(list(anagrams.keys()))

D. anagrams = []
for w in words:
anagrams.append(sorted(w))
print(anagrams)

Solution

1. Step 1: Group words by sorted key using dictionary

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) uses sorted word as key and appends words to list correctly.

2. Step 2: Sort groups by first word

   anagrams = {} for w in words: key = ''.join(sorted(w)) anagrams.setdefault(key, []).append(w) groups = list(anagrams.values()) groups.sort(key=lambda x: x[0]) print(groups) sorts the list of groups by the first word in each group, meeting requirement.

3. Final Answer:

   Correctly groups anagrams using sorted keys, setdefault, append, and sorts groups by first word -> Option B

4. Quick Check:

   Group by sorted key + sort groups by first word = A [OK]

Hint: Use setdefault for grouping and sort groups by first element [OK]

Common Mistakes:

• Using word itself as key loses grouping
• Overwriting dictionary values instead of appending
• Using list instead of dictionary for grouping