@atul: "Given a word and a dictionary find all the anagrams of that word in that dictionary". For efficient access i am storing each word in TRIE with their sorted key. Ex: "BAT" will be inserted with key ABT. By this we will form TRIE of all words.For all the words whose sorted version are same , they will reside at same node.For storing more than one word i am using linked list.
Now for finding anagram of a given word i will just traverse with their corresponding sorted word and will display all the word at that node. Complexity: Each word insertion will take O(m),( sorting can be done in O(m)). If n words are in dictionary then total complexity will be:O(mn). This is the time complexity of building TRIE. Cost of displaying anagram of a word: O(m + d) where d = total output word . Comparison with HASH: With this above approach we are saving time w.r.t. calculating hash key and resolving collision time. Also writing a good hash function is also a challenge. On Sat, Sep 1, 2012 at 6:12 PM, atul anand <atul.87fri...@gmail.com> wrote: > yes but i would like to knw for which application you need this ? > > On 8/31/12, Carl Barton <odysseus.ulys...@gmail.com> wrote: > > There's no reason why a trie or a tree node couldn't be used to > 'represent' > > more than one word. Although you'd take a penalty in the complexity for > > searching etc. > > > > On 31 August 2012 15:33, Navin Kumar <algorithm.i...@gmail.com> wrote: > > > >> Can we store multiple words in single TRIE node by using linked list or > >> some other data structure. Based on the some property a node in TRIE > will > >> hold all the word with same property. > >> > >> -- > >> 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/-/tvqq-_HUZ8sJ. > >> 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. > > -- 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.
