Sign each word such that two words having same signature are anagrams of each other. The signature for every word can be :-> given word in lexicographically sorted order. Keep a trie data structure to store all the signatures. Now every leaf node points to a list having all the words which are anagrams of the corresponding signature. Algo:- take a word and sort a copy of it it lexicographically. Now insert this sorted copy into the trie. If the sorted copy already exists, add the corresponding word to the list pointed by the leaf node. else create a new list and add the word to the list.
Time complexity :- O(N x W) // worst case if all words are unique and no two words are anagrams of each other. N-> total words W-> max word size For example :- "post" , "spot" , "pots" above 2 words have same signature :- "opst" . Hence they are anagram of each other and would be added to the same list. On Friday, 11 May 2012 17:24:01 UTC+5:30, mayur wrote: > > Hi all, > > I am stuck with a question for a long time...can someone provide the best > algorithm for this.. > > Question).. find all the anagrams in a list of words. The algorithm should > be efficient as the list can be very large. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kupYYjDXnbwJ. 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.
