[algogeeks] Re: remove duplicate words from a string
@Ankur In a trie u first insert the first word ..take the second word..If its not present in the trie u insert it else remove it from original string: removing the word requires left shifting the entire string Alternatively u store the elements in a trie in the initial string and terminate it with '\0' and return it: how do we reconstruct the string after creating the trie as we do not know the sequence of words and also some words will contain other words as prefixes. On Oct 11, 2:14 am, Ankur Garg ankurga...@gmail.com wrote: @Sunny..How do u intend to store them in a Tree ? Can you explain ? In a trie u first insert the first word ..take the second word..If its not present in the trie u insert it else remove it from original string .Alternatively u store the elements in a trie in the initial string and terminate it with '\0' and return it . In the worst case trie will take O(n) space where n is the no of letters in the string . and Traversal and creation and search too will take O(n). How abt Balanced Binary Tree ? On Tue, Oct 11, 2011 at 12:38 AM, sunny agrawal sunny816.i...@gmail.comwrote: Trie will take too much space.. Balanced Binary tree can be Better ...?? On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg ankurga...@gmail.com wrote: I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.
[algogeeks] Re: remove duplicate words from a string
a) 1. could split the string using a regexp (into an array) in which you define a word -- is hi. the same as hi, and hi ? 2. then perform a unique operation on the array (some languages have this built in) to remove duplicates 3. recombine array elements into string by joining with a space, for example, depending on how you split it in the first step b) Perhaps another way, in-place, could be to check the string, one word (again define this) at a time, storing each word in a hash. If the hash already contains the word, replace this occurrence with spaces or null bytes. Finally compact the string (remove all null bytes, or turn all extra spaces into one space, etc). icy` On Oct 10, 3:08 pm, sunny agrawal sunny816.i...@gmail.com wrote: Trie will take too much space.. Balanced Binary tree can be Better ...?? On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg ankurga...@gmail.com wrote: I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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.