Cracking the coding interview--Q20.7

Cracking the coding interview--Q20.7

Write a program to find the longest word made of other words.

译文：

写一个程序，找到由其它单词组成的最长单词。

解答

我们从例子着手开始分析问题。假如我们有一个单词数组，如下：

string arr[] = {"test", "tester", "testertest", "testing",              "apple", "seattle", "banana",  "batting", "ngcat",              "batti","bat", "testingtester", "testbattingcat"};

哪一个是题目要求的最长单词？这时候假如你有另一个"我"能跳出来， 观察自己的思考过程。你就会发现自己是怎么去解这个问题的， 然后只需要把你的思考过程变成算法，写成代码就OK了。

题目说要找最长单词，所以你的眼睛自然会去寻找那些长单词，至少你不会从bat 开始找起，对吧。找到最长的单词是testbattingcat， 下一步去看它是否可以由其它单词组成。我们发现test是testbattingcat的一部分， bat也是它的一部分，然后呢？剩下的tingcat不能由其它单词构成。不过， 我们可以用test，batti，ngcat来组成它。所以， 它就是我们要找的可以由其它单词组成的最长单词。

把上面的思考过程转换成算法，可以描述如下：

1. 按单词的长度从大到小排序。(先寻找最长的单词)

2. 不断地取单词的前缀s，当s存在于单词数组中，递归调用该函数， 判断剩余串是否可以由其它单词组成。如果可以，返回true。

对于上面的例子testbattingcat，我们通过不断取前缀：t不在数组中，te不在数组中， tes不在数组中，test在数组中；递归调用去处理剩余串battingcat，b不在数组中， ba不在数组中，bat在数组中；递归调用去处理剩余串tingcat， 发现它所有的前缀都不存在于数组中，退递归来到处理battingcat那一层。 接着上次的bat继续处理：batt不在数组中，batti在数组中；递归调用去处理剩余串 ngcat，n，ng，ngc，ngca都不在数组中，ngcat存在数组中。递归调用处理剩余串， 发现剩余串为空，返回真。

Read full article from Cracking the coding interview--Q20.7