@all .. i suggested him the hashing method... but was not convinced... he might be expecting something else.. something like tries.. etc..
@ Karthikeyan Muthu... can u explain it in detail with some ex ... On Thu, Aug 23, 2012 at 11:28 PM, Karthikeyan Muthu < keyankarthi1...@gmail.com> wrote: > 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. > -- Regards, GAURAV CHAWLA +919992635751 +919654127192 -- 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.
