l*****n 发帖数: 577 | 1 从cacreecup上看来的,amzon家的新题
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. | s******n 发帖数: 3946 | 2 构造prefix tree,然后再匹配每个字串,匹配的过程用到DP(保存中间结果) |
|