[前缀树]leetcode720：词典中最长的单词(easy)

前缀树]leetcode720：词典中最长的单词(easy)"/>

[前缀树]leetcode720：词典中最长的单词(easy)

题目：

题解：

思路1：前缀树

• 最长单词的每个字符在前缀树中对应的节点都能表示一个字符串，还有一点需要注意的是在最长单词的长度相等时，我们需要选择字典序小的单词。然后就是两次遍历字符串数组，第一次遍历是建立前缀树，第二次遍历是寻找最长单词了。

---

思路2：用 set 来判断每个的单词的所有前缀都是否存在。

• 所有前缀存在的话，然后选择一个长度最长的，或者遇到长度相同的字符串，选择字典序更小的那个。

---

思路3：排序

• 排序：先将 words 中的单词进行排序，对于长度不同的单词，按长度由小到大进行排序；对于长度相同的元素，按字典序由大到小进行排序。这样来确保遍历到每个单词时，比它短的前缀都遍历过了，而已每遇到符合要求的单词都是长度最长且字典序最小的单词了。
• 遍历：由于已经排序过了，则当前单词的所有前缀只有在set中，才能进行更新res，而且我们只用判断当前单词的最长前缀即可。

代码如下：

// 思路1：前缀树
class Trie{
private:bool is_string=false;Trie *next[26]={nullptr};
public:Trie(){}void insert(string word){// 插入单词Trie *root=this;for(const auto& w:word){if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();root=root->next[w-'a'];}root->is_string=true;}bool search(string word){// 判断该单词的所有前缀是否由其他所有单词构成Trie *root=this;for(const auto& w:word){// 该前缀不是由其他单词逐步组成的，查找失败if(!root->next[w-'a']->is_string)return false;root=root->next[w-'a'];}return true;}
};
class Solution {
public:string longestWord(vector<string>& words) {Trie *root=new Trie();for(const auto& w:words)root->insert(w);string res;for(const auto& w:words)if(root->search(w)){// 长度不一样，则更新为更长的if(res.size()<w.size())res=w;// 长度一样，则更新为字典序更小的else if(res.size()==w.size())res=min(res,w);}return res;}
};

// 思路2：用 set 来判断是否该单词的所有前缀都存在
class Solution {
public:string longestWord(vector<string>& words) {set<string> s(words.begin(),words.end());string res;for(const auto& w:words){int i,n=w.size();// 判断该单词的前缀是否都存在于words中for(i=0;i<n;++i){if(!s.count(w.substr(0,i+1)))break;}// 该单词的前缀都存在，则判断是否进行更新if(i==n){// 长度不一样，则更新为更长的if(res.size()<w.size())res=w;// 长度一样，则更新为字典序更小的else if(res.size()==w.size())res=min(res,w);}}return res;}
};

// 思路3：排序
class Solution {
public:string longestWord(vector<string>& words) {// 将数组words中的单词排序，对于长度不同的单词，按长度由小到大进行排序；对于长度相同的元素，按字典序由大到小进行排序// 这样来确保遍历到每个单词时，比它短的前缀都遍历过了，而已每遇到符合要求的单词都是长度最长且字典序最小的单词了sort(words.begin(),words.end(),[](const auto& a,const auto& b){return a.size()!=b.size()?a.size()<b.size():a>b;});string res;// 首先加入空字符串unordered_set<string> dict={""};for(const auto& w:words){// 由于已经排序过了，则当前单词的所有前缀只有在set中，才能进行更新res，而且我们只用判断当前单词的最长前缀即可if(dict.count(w.substr(0,w.size()-1))){res=w;dict.insert(w);}}return res;}
};