Problem: Given a dictionary with set of words in it. Write a program to group all words which are anagrams of each other in to sets.
For example –
Input: “bat”, “tar”, “xyz” , “tab”, “tar”
Output:[["bat", tab"], ["tar", rat"],”xyz” ]
Thi sproblem was asked in amazon interview.
Steps:
1)Use some sort of a hash structure.
2) Sort all words alphabetically and use the sorted word as the key
3) If the key is found, keep on adding the original word to the ‘value’ list of strings.
Psuedo code for the problem:
source = ['tab','bat','atb','tac','cat','xyz'] hash_table = {} for x in source: sorted_key = compare_sort(x) print sorted_key if hash_table.has_key(sorted_key): list = hash_table[sorted_key] list.append(x) hash_table[sorted_key] = list else: new_list =[x] hash_table[sorted_key] = new_list return hash_table
public static void groupAnagramWords ()
{
String[] words = {“cat”, “dog”, “tac”, “god”, “act”,”mary”,”Mary”,”army”};
HashMap<Integer, List> hm = new HashMap <Integer, List> ();
for(String val:words){
int hash = getHash(val);
List wordList = new ArrayList ();
if (hm.containsKey(hash))
{
wordList = hm.get(hash);
wordList.add(val);
hm.put(hash,wordList );
}
else
{
wordList.add(val);
hm.put(hash, wordList);
}
}
System.out.println(hm.toString());
}
static int getHash(String val){
char[] c = val.toCharArray();
int hash = 0;
for(char ch:c){
String sc = String.valueOf(ch);
hash=hash+sc.hashCode();
}
return hash;
}