【数据结构-Trie树】力扣720. 词典中最长的单词

给出一个字符串数组 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就是答案。