# Group anagrams together from a list of words

Given a list of words, efficiently group all anagrams.

The two strings, `X` and `Y`, are anagrams if by rearranging `X's` letters, we can get `Y` using all the original letters of `X` exactly once. For example, all these pairs are anagrams as lhs can be rearranged to rhs and vice-versa.

actors = costar
altered = related
auctioned = education
aspired = despair
mastering = streaming
recurd = secured

The problem requires the anagrams to be grouped together. For example,

Input:

[CARS, REPAID, DUES, NOSE, SIGNED, LANE, PAIRED, ARCS, GRAB, USED, ONES, BRAG, SUED, LEAN, SCAR, DESIGN]

Output:

GRAB BRAG
CARS ARCS SCAR
REPAID PAIRED
LANE LEAN
SIGNED DESIGN
DUES USED SUED
NOSE ONES

Practice this problem

The idea is to sort each word on the list and construct a map where the map’s key is each sorted word, and the map’s value is a list of indices in the array where it is present. After creating the map, traverse the map and get indices for each sorted key. The anagrams are present in the actual list at those indices.

Following is the C++, Java, and Python implementation of the idea:

Output:

ARCS CARS SCAR
BRAG GRAB
DESIGN SIGNED
DUES SUED USED
LANE LEAN
NOSE ONES
PAIRED REPAID

## Java

Output:

[REPAID, PAIRED]
[BRAG, GRAB]
[SUED, USED, DUES]
[LEAN, LANE]
[CARS, SCAR, ARCS]
[NOSE, ONES]
[DESIGN, SIGNED]

## Python

Output:

(‘CARS’, ‘ARCS’, ‘SCAR’)
(‘REPAID’, ‘PAIRED’)
(‘DUES’, ‘USED’, ‘SUED’)
(‘NOSE’, ‘ONES’)
(‘SIGNED’, ‘DESIGN’)
(‘LANE’, ‘LEAN’)
(‘GRAB’, ‘BRAG’)

We can also use multimap to solve this problem, as demonstrated below:

## C++

Output:

ARCS CARS SCAR
BRAG GRAB
DESIGN SIGNED
DUES SUED USED
LANE LEAN
NOSE ONES
PAIRED REPAID

The time complexity of the above solutions is O(N × M × log(M)), where `N` is the total number of words and `M` is the size of the longest word in the list.

Rate this post

Average rating 4.88/5. Vote count: 184

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?