『字典树』词典中最长的单词720

题目相关

• 原题链接：720. 词典中最长的单词 - 力扣（LeetCode）
• 涉及知识：字典树
• 题目难度：★

题目解读

根据题意，非常直观的一个方法是通过构造字典树来求解，对数据先排序或者根据条件不断更新结果。这里提供一个另类的模拟字典树的实现，省去了将全部word都插入到Trie树中，而是先对数据根据长度与字符大小排序，然后在遍历数据时，同时进行判断和插入的操作。然而这里对数据先排序同时也增加了算法的时空复杂度。

Python相关

由于Python并没有提供内置的Trie树实现，所以在代码中要手动模拟实现

具体实现

自己提出的版本:

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()
        words.sort(key=len)
        
        trie = {}
        result = ''
        for word in words:
            flag = True
            temp = trie
            for letter in word[:-1]:
                if letter not in temp:
                    flag = False
                    break
                else:
                    temp = temp[letter]
            if flag:
                temp[word[-1]] = {}
                if len(word) >len( result):
                    result = word
        return result

他人方案中较好的前缀树实现方案：

class Solution:
    def longestWord(self, words: List[str]) -> str:
        res=''
        trie=Trie()
        for word in words:
            trie.insert(word)
        for word in words:
            if trie.search(word):
                if len(word) > len(res):
                    res=word
                elif len(word)==len(res) and word < res:
                    res=word
        return res

class TrieNode:
    def __init__(self):
        self.end=False
        self.children=collections.defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root=TrieNode()

    def insert(self, word: str) -> None:
        node=self.root
        for s in word:
            node=node.children[s]
        node.end=True

    def search(self, word: str) -> bool:
        node=self.root
        for s in word:
            node=node.children.get(s)
            if node is None or not node.end:
                return False
        return True

另外一个挺不错的应用贪心算法（将所有的words根据长度分组，然后从小到大依次看后一个组的单词的[:-1]部分是否在前一个组中）的思路，值得借鉴！
同时该代码也有值得改进之处，比如说dict作为内置关键字不应该作为变量名来使用，同时用set分组比list分组在查找上效率要高一些。

class Solution:
    def longestWord(self, words: List[str]) -> str:
        dict = [[] for _ in range(31)]
        for word in words:
            dict[len(word)].append(word)

        longestword = set(dict[1])
        for i in range(2, 31):
            tmp = [w for w in dict[i] if w[:-1] in longestword]
            if not tmp:
                break
            longestword = tmp

        return sorted(longestword)[0]