i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows:
1) Create a trie <http://en.wikipedia.org/wiki/Trie> representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] > 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel <ashg...@gmail.com> wrote: > yes, that is correct. > O(mn) to form multimap and then O(m) to tell all anagram groups > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Thu, Aug 23, 2012 at 5:11 PM, kings <dns.bhar...@gmail.com> wrote: > >> Dear GC, >> >> The efficient data structure in my opinion is Hash Table. >> >> 1. For a given word in the dictionary we need to form an anagram >> dictionary i.e. take a given word sort it which forms the key for the >> hashtable , then start forming the different anagrams for that word and >> insert it into the hash table with the corresponding key. >> >> 2. Once the hash table is ready for the given word sort it find the key >> and print all the anagarams i.e. values associated to that key. we will get >> all the anagrams for a given word. >> >> Coming to time complexity... >> >> sorting of a word can be done in a O(nlogn). >> building of anagram will take O(n). >> hash complexity O(n) worst case. >> so total time complexity is O(nlogn) for whole execrcise. >> >> Thanks >> Bhargava >> >> >> On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: >>> >>> Ques.. >>> >>> Given a m-word dictionary ... and a n-sized word... .. now suggest DS >>> for dictionary such that you can find out all the anagrams of the given >>> word present in dictionary... >>> >>> >>> -- >>> Regards, >>> G C >>> >>> >>> >>> -- >> 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/-/ySPUSvS0Sh0J. >> >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
