题目
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
示例 1：
输入：words = ["w","wo","wor","worl", "world"] 输出："world" 解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
示例 2：
输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 输出："apple" 解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
解题
方法一：字典树
- 1.排序，按字符长度少的在前，如果相等，字典序小的在前
- 2.如果长度为1的，直接插入trie；如果长度大于1的时候，满足长度l-1的字符也能在trie中找到，才能插入trie。
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){ int l=word.size(); if(l==1){ if(l>maxSize){ maxSize=1; res=word; } insert(word);//长度为1的时候都可以插入 continue; } if(dfs(word.substr(0,l-1),0)){ if(l>maxSize){ maxSize=l; res=word; } insert(word);//长度大于1的时候，必须满足长度为l-1的能在字典树中找到 } } 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) return true; else 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; } };
写法二：
struct Trie{ bool isEnd; vector<Trie*> next; Trie(){ isEnd=false; next=vector<Trie*>(26,nullptr); } }; class Solution { public: Trie* trie=new Trie(); void insert(string& s){ Trie* node=trie; for(char c:s){ if(!node->next[c-'a']) node->next[c-'a']=new Trie(); node=node->next[c-'a']; } node->isEnd=true; } bool dfs(string& word){ Trie* node=trie; for(int i=0;i<word.size()-1;i++){ char c=word[i]; if(node->next[c-'a']) node=node->next[c-'a']; else return false; if(node->isEnd==false) return false; } return true; } string longestWord(vector<string>& words) { sort(words.begin(),words.end(),[](string& a,string& b){ return a.size()<b.size(); }); string res; for(string& word:words){ if(dfs(word)){ if(word.size()>res.size()){ res=word; }else if(word.size()==res.size()&&word<res){ res=word; } } insert(word); } return res; } };
