720 词典中最长的单词（Trie树）

一时失言乱红尘 2022-09-09 12:51 212阅读 0赞

**1. 问题描述：**

给出一个字符串数组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

**2. 思路分析：**

分析题目可以知道我们需要求解出所有单词最长的前缀，根据这个特点可以知道我们可以使用**Trie树**来解决，Trie树适合求解字符串的插入与前缀查询操作。因为使用的是python语言所以我们可以声明一个二维列表son（c++/java等语言可以声明二维数组），其中第一维的长度为N，N为Trie树中节点的个数，由题目可知words长度为1000，每个单词长度为30所以Trie树中节点个数最多为1000 \* 30 = 30000，所以第一维声明比30000长一点即可（可以将每一个字符看成是Trie树中的一个节点），第一维表示当前字符串的前缀对应的编号，第二维表示当前字符串结尾的字符对应的位置，长度为26表示26个字母对应的位置，我们需要借助于一个int类型的变量idx来唯一标识Trie树中的每一个节点，这样第一维的编号p加上当前编号对应单词的结尾字符就可以判断出对应前缀是否存在。并且我们需要声明一个一维列表is\_end来记录插入节点的时候对应单词的编号，这样我们在后面找对应答案的时候可以根据当前的节点编号p找到对应的单词编号；查询最长的前缀的时候我们可以使用dfs搜索整棵Trie树（并且Trie树中先搜索到的节点一定是字典序最小的节点），从Trie树中的第一个节点出发，搜索Trie树中存在的节点，并且对应的节点编号在is\_end中存在则往下递归搜索，is\_end中对应的编号p存在说明words中是存在当前节点编号对应的单词的，也即搜索有结束标记的节点才是有效的，我们可以从上往下搜索Trie树，并且递归返回到上一层调用位置的时候通过递归的结果来更新上一层节点对应的长度以及对应的单词位置，由下往上更新这样最终到Trie树根节点的时候就已经求解出最长的前缀以及在words中对应的编号，返回这个编号即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        son = None
        N = 30010
        # idx用来唯一标识Trie树中的每一个节点
        idx = 0
        # 用来记录后面的答案, 表示的是哪一个单词, is_end[p]表示p这个节点对应的单词编号
        is_end = None
    
        # Trie树中插入节点的操作, k用来标记插入的是哪一个单词
        def insert(self, w: str, k: int):
            son = self.son
            is_end = self.is_end
            p = 0
            for c in w:
                t = ord(c) - ord("a")
                if son[p][t] == 0:
                    son[p][t] = self.idx
                    self.idx += 1
                p = son[p][t]
            # 当前p这个点对应当前单词的下标
            is_end[p] = k
    
        # dfs搜索Trie树, 走有对应单词标记的节点
        def dfs(self, l: int, p: int):
            res = [l, self.is_end[p]]
            for i in range(26):
                j = self.son[p][i]
                if j > 0 and self.is_end[j] != -1:
                    t = self.dfs(l + 1, self.son[p][i])
                    # 往下走发现答案更大那么更新答案第一个找到的答案肯定是字典序最小的
                    if t[0] > res[0]: res = t
            return res
    
        def longestWord(self, words: List[str]) -> str:
            # 初始化Trie树的所有节点
            self.son = [[0] * 26 for i in range(self.N)]
            self.idx = 1
            # 用来记录每一个节点对应单词的下标
            self.is_end = [-1] * self.N
            for i in range(len(words)):
                self.insert(words[i], i)
            # 搜索整棵树
            t = self.dfs(0, 0)
            if t[1] != -1: return words[t[1]]
            return ""

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/dcc3882542bb41fe8097aa9d2112e036.png