Python Program to Group Anagrams from List

Use a dictionary with sorted strings as keys to group anagrams from a list in Python, like groups = defaultdict(list); for word in words: groups[''.join(sorted(word))].append(word).

Examples

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

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

Input["abc", "bca", "cab", "xyz", "zyx"]

Output[["abc", "bca", "cab"], ["xyz", "zyx"]]

Input[]

Output[]

How to Think About It

To group anagrams, think of each word's letters sorted alphabetically. Words that are anagrams will have the same sorted letters. Use this sorted form as a key to collect all words that match it.

Algorithm

1

Create an empty dictionary to hold groups of anagrams.

2

For each word in the list, sort its letters alphabetically.

3

Use the sorted letters as a key in the dictionary.

4

Append the original word to the list of words for that key.

5

After processing all words, return the list of grouped anagrams.

Code

python

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = ''.join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))

Output

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

Dry Run

Let's trace the list ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] through the code

1

Initialize groups dictionary

groups = {} (empty)

2

Process word 'eat'

sorted('eat') = 'aet'; groups = {'aet': ['eat']}

3

Process word 'tea'

sorted('tea') = 'aet'; groups = {'aet': ['eat', 'tea']}

4

Process word 'tan'

sorted('tan') = 'ant'; groups = {'aet': ['eat', 'tea'], 'ant': ['tan']}

5

Process word 'ate'

sorted('ate') = 'aet'; groups = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}

6

Process word 'nat'

sorted('nat') = 'ant'; groups = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}

7

Process word 'bat'

sorted('bat') = 'abt'; groups = {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

8

Return grouped anagrams

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

Word	Sorted Key	Groups Dictionary
eat	aet	{'aet': ['eat']}
tea	aet	{'aet': ['eat', 'tea']}
tan	ant	{'aet': ['eat', 'tea'], 'ant': ['tan']}
ate	aet	{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
nat	ant	{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
bat	abt	{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

Why This Works

Step 1: Sorting letters creates a unique key

Sorting the letters of each word puts anagrams into the same order, so they share the same key.

Step 2: Dictionary groups words by sorted key

Using the sorted word as a dictionary key collects all anagrams together in a list.

Step 3: Return all grouped anagrams

The dictionary values are lists of anagrams, which we return as the final grouped result.

Alternative Approaches

Using a normal dictionary with tuple keys

python

def group_anagrams(words):
    groups = {}
    for word in words:
        key = tuple(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))

Using tuple keys avoids joining strings but works similarly; performance difference is minimal.

Using collections.Counter as key

python

from collections import defaultdict, Counter

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = tuple(sorted(Counter(word).items()))
        groups[key].append(word)
    return list(groups.values())

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))

Using letter counts as keys handles anagrams but is slower due to counting overhead.

Complexity: O(n * k log k) time, O(n * k) space

Time Complexity

Sorting each word of length k takes O(k log k), done for n words results in O(n * k log k).

Space Complexity

Extra space is used for the dictionary storing all words grouped by keys, up to O(n * k).

Which Approach is Fastest?

Using sorted strings as keys is simple and efficient; using Counters is slower due to counting overhead.

Approach	Time	Space	Best For
Sorted string keys	O(n * k log k)	O(n * k)	Simple and fast grouping
Tuple of sorted letters	O(n * k log k)	O(n * k)	Similar to string keys, avoids string join
Counter-based keys	O(n * k log k)	O(n * k)	Handles complex anagrams but slower