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
recused = 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 indexes in the array where it is present. After creating the map, we traverse the map and get indexes for each sorted key. The anagrams are present in actual list at those indexes.

 
C++ implementation –
 

Download   Run Code

Output:

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

 

We can also use std::unordered_multimap instead of std::unordered_map> to solve this problem.

 
C++ implementation –
 

Download   Run Code

Output:

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

 

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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz