Group all Words in Set of Anagrams of Each Other in Dictionary

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 

One Thought on “Group all Words in Set of Anagrams of Each Other in Dictionary

  1. Balaji Thiruvengadam on August 6, 2015 at 11:43 am said:

    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;
    }

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation