/* 1.hashtable 把每个字符串都放到hashtable中
a.排序 长度不同，长的放在前面，长度相同，字典序小的放在前面
b.不排序 遍历数组，对于每个字符串判断它的所有前缀是否都在hashtable中，如果排序的话，满足条件就返回； 不排序的话，需要遍历所有，比较长度和字典序
2.trie树 把每个字符串插入到trie树中
a.排序
b.不排序 遍历数组，查询所有前缀是否在trie树中，而且要求节点标志位为 字符串结尾标志 */
方法一 通过排序和哈希set存储字符串前缀：
class Solution { public: string longestWord(vector<string>& words) { set<string> se;//从单个字母逐渐加1填充，用于next的前一个词缀是否存在的表现。 sort(words.begin(),words.end()); int len=words.size(); string res,flag; if(len==0 || words[0].size()==0) return ""; int start=0; while(words[start].size()>1){ start++; } flag=words[start]; for(int i=start;i<len;i++){ se.insert(flag); //判断是否符合函数关系 //cout<<flag<<","<<res<<endl; //cout<<words[i]<<","; string tmp=words[i]; tmp.pop_back(); if(se.count(tmp)){ flag=words[i]; } //判断一个单元是否到达边界，并判断是否更改返回值 //cout<<flag<<" "<<res<<endl; if(flag.size()>res.size()) res=flag; if(words[i].size()==1) flag=words[i]; } return res; } };
方法二 使用字典树：
//定义字典树节点 class TrieNode{ public: TrieNode *child[26]; bool isend=false; TrieNode(){ for(int i=0;i<26;i++){ child[i]=NULL; } } }; //定义字典树 class Trie{ public: TrieNode* root; Trie(){ root=new TrieNode(); } void insert(string words){ TrieNode *p=root; for(auto w:words){ int i=w-‘a‘; if(p->child[i]==NULL) p->child[i]=new TrieNode(); p=p->child[i]; } p->isend=true; } bool searchevery(string words){ TrieNode *p=root; for(auto w:words){ int i=w-‘a‘;
//查询words从一个字母开始的每一个前缀是否在trie树中，不在的话return false if(p->child[i]==NULL || p->child[i]->isend==false) return false; p=p->child[i]; } return true; } }; class Solution { public: string longestWord(vector<string>& words) { string res; Trie trie; for(auto word:words){ trie.insert(word); } for(auto w:words){ if(trie.searchevery(w)&&(w.size()>res.size()||(w.size()==res.size()&&w<res))) res=w; } return res; } };
原文：https://www.cnblogs.com/joelwang/p/10831950.html