写一个程序，找到由其它单词组成的最长单词
问题：写一个程序，找到由其它单词组成的最长单词；
解答：
我们从例子着手开始分析问题。假如我们有一个单词数组，如下：
"test""tester""testertest""testing""apple""seattle""banana""batting""ngcat""batti""bat""testingtester""testbattingcat"#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)。
注意上述代码中有一句：
if(i == length) return false;//取到原始串，即自身意思是当我们取一个单词前缀，最后取到整个单词时， 这种情况就认为是没有其它单词可以组成它。如果不要这一句， 那么你在哈希表中总是能查找到和它自身相等的串(就是它自己)，从而返回true。 而这明显不是我们想要的。我们要的是其它单词来组成它，不包括它自己。
这样一来，又引出一个问题，如果单词中就是存在两个相同的单词。 比如一个单词数组中最长的单词是abcdefg，并且存在2个，而它又不能被更小的单词组成， 那么我们可以认为这个abcdefg是由另一个abcdefg组成的吗？ 关于这一点，你可以和面试官进行讨论。(上述代码认为是不能的。)
由于使用哈希表会占用较多空间，一种不使用额外空间的算法是直接在单词数组中查找， 由于单词数组已经按长度从大小到排，因此单次查找时间为O(n)。一共有n个单词， 平均长度为d，所以总共需要的时间为O(nd*n)=O(dn2 )。 如果我们再开一个数组来保存所有单词，并将它按字典序排序， 那么我们可以使用二分查找，单次查找时间变为O(logn)，总共需要O(dnlogn)。