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
Output[[1,3],[2],[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
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
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; } } |
Output
We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.