Group Anagrams Together from given List of Words

Given a list of words, efficiently group all anagrams together.

 

X and Y are anagrams if by rearranging the letters of X, 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
recursed = 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

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

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Output:

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

 

Java

Download   Run Code

Output:

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

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

C++

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 
The time complexity of above solutions is O(nmlogm) where n is number of words and m is size of longest word in the list.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of