给出一个字符串数组 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 <= words.length <= 1000
1 <= words[i].length <= 30
所有输入的字符串 words[i] 都只包含小写字母。

字典树

class Solution {
private:struct trie{vector<trie*> children;bool isEnd;trie():children(26, nullptr), isEnd(false){};};trie* root;public:Solution(){root = new trie();};string longestWord(vector<string>& words) {for(string word : words){trie* node = root;for(char ch : word){ch -= 'a';if(node->children[ch] == nullptr){node->children[ch] = new trie();}node = node->children[ch];}node->isEnd = true;}string longest = "";for(int i = 0; i < 26; i++){if(root->children[i] != nullptr && root->children[i]->isEnd){findWord(root->children[i], string(1, i + 'a'), longest);}    }return longest;}void findWord(trie* node, string wd, string &longest){if(wd.size() > longest.size()){longest = wd;}else if(wd.size() == longest.size()){if(wd < longest){longest = wd;}}for(int i = 0; i < 26; i++){if(node->children[i] != nullptr && node->children[i]->isEnd){findWord(node->children[i], wd + char('a' + i), longest);}}}
};

这道题的思路就是我们先用words里的所有单词构造出一个字典树，并且在字典树中用isEnd来标记该字符是否是某个单词结尾。

构造完字典树后，我们从树的根节点开始递归，用longest来记录最长的单词，我们在递归中只有子节点不是空指针，并且子节点的isEnd是true的时候，才会将递归子节点。我们在递归函数中有三个参数，分别是node代表当前节点，wd代表当前路径得到的单词，longest代表该节点递归前的最长longest是多少。也就是说，node和wd是在检验没问题后才传入递归函数，而longest需要与当前的单词wd进行比较，如果wd长度更长，则更新longest，如果wd长度等于longest并且字典序更小，也更新longest。由于longest是直接引用外部变量，在递归中会不断更新longest，所以我们最终直接返回longest就是答案。