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 <[email protected]> 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 [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. > -- 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.
