You could do this too... 1. Sort the words based on length. Max Time: O(nlogn) 2. Now, Create a tree similar to a state transition diagram. For each word in the tree, store their start and end pointers. 3. If a word comprises of another word, then the main word would only store start and end pointers for the enclosed word. For example in the tree , the word catsdogcats, will stored as original cats+pointer to start and end of dog+pointer to start and end of cats
Even if all the words are different, this construction will not take you more then O(n*w) time where w is the maximum length of any word. 4. Finding the longest word which can be constructed using other words can either be done online i.e. while constructing the tree or after constructing the tree, we do it for each unique branch of the tree. Max Time: O(n*I) Hence. total time: O(n log n) On Tue, May 20, 2008 at 1:56 PM, anshu <[EMAIL PROTECTED]> wrote: > > This question aint clear > So, for example in above list hippopotamuses is also in the list of > word in the file. > So this word includes itself and is 14 characters. > where is a condition that concatenation is a must? > > > > On May 20, 3:39 am, greg <[EMAIL PROTECTED]> wrote: > > Write a program that reads a file containing a sorted list of > > words (one word per line, no spaces, all lower case), then identifies > > the > > longest word in the file that can be constructed by concatenating > > copies of > > shorter words also found in the file. > > > > For example, if the file contained: > > > > cat > > cats > > catsdogcats > > catxdogcatsrat > > dog > > dogcatsdog > > hippopotamuses > > rat > > ratcatdogcat > > > > The answer would be 'ratcatdogcat' - at 12 letters, it is the longest > > word made up of other words in the list. > > > > I'm having trouble coming up with anything other than starting with > > the longest word in the list and checking for each of the other words > > in the list, which seems incredibly inefficient, any ideas or > > suggestions of things to look at? > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
