题目
原文：
Write a program to find the longest word made of other words.
译文：
写一个程序，找到由其它单词组成的最长单词。
解答
我们从例子着手开始分析问题。假如我们有一个单词数组，如下：
1
2
3
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来组成它。所以， 它就是我们要找的可以由其它单词组成的最长单词。
把上面的思考过程转换成算法，可以描述如下：
-
按单词的长度从大到小排序。(先寻找最长的单词)
-
不断地取单词的前缀s，当s存在于单词数组中，递归调用该函数， 判断剩余串是否可以由其它单词组成。如果可以，返回true。
对于上面的例子testbattingcat，我们通过不断取前缀：t不在数组中，te不在数组中， tes不在数组中，test在数组中；递归调用去处理剩余串battingcat，b不在数组中， ba不在数组中，bat在数组中；递归调用去处理剩余串tingcat， 发现它所有的前缀都不存在于数组中，退递归来到处理battingcat那一层。 接着上次的bat继续处理：batt不在数组中，batti在数组中；递归调用去处理剩余串 ngcat，n，ng，ngc，ngca都不在数组中，ngcat存在数组中。递归调用处理剩余串， 发现剩余串为空，返回真。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include "hash.h"
using namespace std;
Hash hash;
inline bool cmp(string s1, string s2){//按长度从大到小排
return s2.length() < s1.length();
}
bool MakeOfWords(string word, int length){
//cout<<"curr: "<<word<<endl;
int len = word.length();
//cout<<"len:"<<len<<endl;
if(len == 0) return true;
for(int i=1; i<=len; ++i){
if(i == length) return false;//取到原始串，即自身
string str = word.substr(0, i);
//cout<<str<<endl;
if(hash.find((char*)&str[0])){
if(MakeOfWords(word.substr(i), length))
return true;
}
}
return false;
}
void PrintLongestWord(string word[], int n){
for(int i=0; i<n; ++i)
hash.insert((char*)&word[i][0]);
sort(word, word+n, cmp);
for(int i=0; i<n; ++i){
if(MakeOfWords(word[i], word[i].length())){
cout<<"Longest Word: "<<word[i]<<endl;
return;
}
}
}
int main(){
string arr[] = {"test", "tester", "testertest", "testing",
"apple", "seattle", "banana", "batting", "ngcat",
"batti","bat", "testingtester", "testbattingcat"};
int len = 13;
PrintLongestWord(arr, len);
return 0;
}
上述代码将单词存放在哈希表中，以得到O(1)的查找时间。排序需要用O(nlogn)的时间， 判断某个单词是否可以由其它单词组成平均需要O(d)的时间(d为单词长度)， 总共有n个单词，需要O(nd)的时间。所以时间复杂度为：O(nlogn + nd)。 n比较小时，时间复杂度可以认为是O(nd)；n比较大时，时间复杂度可以认为是O(nlogn)。
注意上述代码中有一句：
1
if(i == length) return false;//取到原始串，即自身
意思是当我们取一个单词前缀，最后取到整个单词时， 这种情况就认为是没有其它单词可以组成它。如果不要这一句， 那么你在哈希表中总是能查找到和它自身相等的串(就是它自己)，从而返回true。 而这明显不是我们想要的。我们要的是其它单词来组成它，不包括它自己。
这样一来，又引出一个问题，如果单词中就是存在两个相同的单词。 比如一个单词数组中最长的单词是abcdefg，并且存在2个，而它又不能被更小的单词组成， 那么我们可以认为这个abcdefg是由另一个abcdefg组成的吗？ 关于这一点，你可以和面试官进行讨论。(上述代码认为是不能的。)
由于使用哈希表会占用较多空间，一种不使用额外空间的算法是直接在单词数组中查找， 由于单词数组已经按长度从大小到排，因此单次查找时间为O(n)。一共有n个单词， 平均长度为d，所以总共需要的时间为O(nd*n)=O(dn^2 )。 如果我们再开一个数组来保存所有单词，并将它按字典序排序， 那么我们可以使用二分查找，单次查找时间变为O(logn)，总共需要O(dnlogn)。
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/03/04/20.7/
