题目
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： ["cat","banana","dog","nana","walk","walker","dogwalker"] 输出： "dogwalker" 解释： "dogwalker"可由"dog"和"walker"组成。
解题
方法一：字典树+dfs
首先排序，长度小的放前面，如果长度相等，字典序小的放前面。
如果从头开始遍历，因为相同长度，字典序小的会取到。
class Trie{ public: bool isEnd=false; vector<Trie*> next=vector<Trie*>(26,nullptr); }; class Solution { public: Trie* trie=new Trie(); string longestWord(vector<string>& words) { sort(words.begin(),words.end(),[](string& a,string& b){ if(a.size()==b.size()) return a<b;//如果长度相等，字典序小的放前面 return a.size()<b.size();//长度小的放前面 }); int maxSize=0; string res=""; for(string& word:words){ if(dfs(word,0)){ if(word.size()>maxSize){ maxSize=word.size(); res=word; } } else insert(word); } return res; } bool dfs(string& word,int startIndex){ if(startIndex==word.size()) return true; Trie* node=trie; for(int i=startIndex;i<word.size();i++){ char c=word[i]; if(node->next[c-'a']){ node=node->next[c-'a']; }else return false; if(node->isEnd){ if(dfs(word,i+1)) return true; } } return false; } void insert(string& word){ Trie* node=trie; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; } node->isEnd=true; } };
