720. 词典中最长的单词

Difficulty
easy
Tags
前缀树
URL
https://leetcode.cn/problems/longest-word-in-dictionary/
Star
给出一个字符串数组 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 Node:
    def __init__(self):
        self.child = {}
        self.is_word = None

class Trie:
    def __init__(self):
        self.root = Node()
        self.root.is_word = ""

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.child:
                node.child[char] = Node()
            node = node.child[char]
        node.is_word = word

class Solution:
    def longestWord(self, words: List[str]) -> str:
        self.tree = Trie()
        for word in words:
            self.tree.insert(word)
        self.res = ""
        self.helper(self.tree.root)
        return self.res

    def helper(self, node):
        if node.is_word is None:
            return
        
        if len(node.is_word) > len(self.res):
            self.res = node.is_word
        elif len(node.is_word) == len(self.res):
            self.res = min(self.res, node.is_word)

        for _, nxt_node in node.child.items():
            self.helper(nxt_node)