Create a Hash Table, start parsing the file.. Compute a unique decimal value for each word, inspired by the Rabin Karp method. Use this decimal value as the key for the Hash Table, insert it into the table, on collisions increment the anagram count or create a linked list to store each anagram.
I don't know what you men by linear space complexity but this will work in linear time ( assuming there is a perfect hash ) On Wed, Nov 30, 2011 at 11:57 AM, KARTHIKEYAN V.B. <[email protected]>wrote: > Find the set of anagrams from a file of english words > [Hint: anagrams are permutation of the word eg: "ate" , "eat" , > "tea" are all anagrams] > in linear time and space. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
