Given an array of strings, return all groups of strings that are anagrams. Represent a group by a list of integers representing the index in the original list. Look at the sample case for clarification.

Anagram : a word, phrase, or name formed by rearranging the letters of another, such as ‘spar’, formed from ‘rasp’

Example

Input[“abc”,”gh”,”bca”,”ac”]
Output[[1,3],[2],[4]]

abc and bca are anagrams which correspond to index 1 and 3.

gh and ac are not anagrams with other words, however word itself is anagram hence we have groups for index 2 and 4.

Result group should have index ordered Lexicographically, if Strings at index i,j and k are anagrams to each other than result group having index sequence as [i,j,k] if i<j<k.

Solution

We can build a HashMap of String with List of Result Group. We can transform each Word to the common String by doing sorting on each Character. For example word “cat” will be transformed to “act”.

A transformed key can be used as a key in Hashmap and ArrayList of Integer can hold indexes of words matching to the key.

Code

Output

[[6], [1, 2, 5], [3, 4]]

We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *