Group Anagrams Using Hash Map in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an anagram?

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

beginner

Why do we use a hash map to group anagrams?

We use a hash map to group anagrams because it allows us to store words with the same sorted letters as the key, making it easy to collect all anagrams together efficiently.

beginner

How do you create a key for the hash map when grouping anagrams?

You create the key by sorting the letters of the word alphabetically. For example, 'eat' becomes 'aet'. All anagrams share the same sorted key.

intermediate

What is the time complexity of grouping anagrams using a hash map?

The time complexity is O(N * K log K), where N is the number of words and K is the maximum length of a word, because sorting each word takes O(K log K).

beginner

Explain the main steps to group anagrams using a hash map.

1. Initialize an empty hash map.
2. For each word, sort its letters to create a key.
3. Add the original word to the list of values for that key.
4. After processing all words, the hash map values are groups of anagrams.

What is the key used in the hash map when grouping anagrams?

A The original word itself

B The length of the word

C The first letter of the word

D The sorted letters of the word

The key is the sorted letters of the word because all anagrams share the same sorted letter sequence.

Which data structure is best for grouping anagrams efficiently?

A Stack

B Queue

C Hash map (dictionary)

D Linked list

A hash map allows quick grouping by keys, making it ideal for grouping anagrams.

What is the main operation done on each word to find its group?

A Sorting the letters

B Reversing the word

C Counting vowels

D Finding the length

Sorting the letters creates a uniform key for all anagrams.

If the input list is ['bat', 'tab', 'eat', 'tea'], how many groups of anagrams will be formed?

A 1

B 2

C 3

D 4

There are two groups: ['bat', 'tab'] and ['eat', 'tea'].

What is the output format after grouping anagrams?

A A list of lists, each containing anagrams

B A single string with all words

C A sorted list of words

D A count of anagrams

The output is a list of lists, where each inner list contains words that are anagrams of each other.

Describe how you would group a list of words into anagrams using a hash map.

Think about how sorting helps identify anagrams.

Explain why sorting each word is important in grouping anagrams.

Consider what makes anagrams similar.

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