Group anagrams together from a list of words

Google Translate Icon

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:

C++


Download  Run Code

Output:

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

Java


Download  Run Code

Output:

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

Python


Download  Run Code

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++


Download  Run Code

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?




Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding :)



Subscribe
Notify of
guest
6 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Do NOT follow this link or you will be banned from the site!