题目描述

给出一个字符串数组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”。
注意:

所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(Trie + DFS) $O(n^2)$

题解：考虑到前缀相关的题目，我们考虑使用trie树数据结构来解题。首先将词典中的词都插入Trie树中，然后我们从根节点开始，DFS遍历所有是单词的节点（不仅仅是有这个节点，而且这个节点必须是单词节点，因为我们需要一次添加一个字符）。每次遍历到一个节点时，当前路径上的字符就是一个合法的单词，我们将当前单词和当前答案进行比较，如果长度大于当前答案，我们就更新答案。因为我们DFS遍历是就是先遍历字典序较小的那个，如果后面遇到了长度相等的那个一定字典序更大，不是我们想要的答案。

时间复杂度分析：建立Trie树$O(nL)$,DFS遍历也是$O(nL)$，所以总的时间复杂度就是$O(nL$

C++ 代码

class Solution {
public:
    const static int N = 30000;
    int son[N][26],cnt[N],idx = 0,m = 0;
    string res = "";
    string longestWord(vector<string>& words) {
        for(auto word:words) insert(word);
        string cur = "";
        dfs(0,0,cur);
        return res;
    }
    void dfs(int u,int l,string &cur)
    {
        if(l > m){res = cur;m = l;}
        for(int i = 0 ; i < 26 ; i ++)
        {
            int sub = son[u][i];
            if(sub != 0 && cnt[sub] > 0)
            {
                cur += ('a' + i);
                dfs(sub,l + 1,cur);
                cur.pop_back();
            }
        }
    }
    void insert(string s)
    {
        int p = 0 ;
        for(auto c :s)
        {
            int u = c - 'a';
            if(son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }
    bool search(string s)
    {
        int p = 0;
        for(auto c: s)
        {
            int u = c - 'a';
            if(son[p][u] == 0) return false;
            p = son[p][u];
        }
        return cnt[p] > 0;
    }
};