Group all anagrams from a given array of Strings

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


import java.util.*;

public class Anagram {

	public static void main(String[] args) {

		String[] a = { "caat", "taac", "dog", "god", "acta", "bat" };
		System.out.println(new Anagram().anagrams(Arrays.asList(a)));

	}

	public static ArrayList<ArrayList<Integer>> anagrams(final List<String> a) {
		// Result Array
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();

		for (int i = 0; i < a.size(); i++) {
			
			/**
			 * Converting String to Char array to sort the same.
			 * Again we are creating a String from Char array so at the end any Anagram string will have unique form.
			 * For Example:
			 * "caat" and "taac" will be formed to "aact" after sorting the array. 
			 */
			char[] c = a.get(i).toCharArray();
			Arrays.sort(c); 
			String t = String.valueOf(c);
			
			//check if key is present than add to the existing group else create new.
			if (map.get(t) == null) {
				ArrayList<Integer> l = new ArrayList<Integer>();
				l.add(i + 1);
				map.put(t, l);
			} else
				map.get(t).add(i + 1);
		}
		
		// Iterate map to add final result groups to result array.
		for (ArrayList<Integer> l : map.values()) {		
			result.add(l);	
		}

		return result;
	}

}