| 题目链接 | 720. 词典中最长的单词 |
|---|---|
| 思路 | Trie树的经典应用 |
| 题解链接 | 官方题解 |
| 关键点 | 构建Trie树 |
| 时间复杂度 | \(O(\sum_{i}\#\text{word}_{i})\) |
| 空间复杂度 | \(O(\sum_{i}\#\text{word}_{i})\) |
代码实现：
class Trie:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
def insert(self, word):
node = self
for ch in word:
ch = ord(ch) - ord("a")
if not node.children[ch]:
node.children[ch] = Trie()
node = node.children[ch]
node.isEnd = True
def search(self, word):
node = self
for ch in word:
ch = ord(ch) - ord("a")
if node.children[ch] is None or not node.children[ch].isEnd:
return False
node = node.children[ch]
return True
class Solution:
def longestWord(self, words: List[str]) -> str:
tree = Trie()
for word in words:
tree.insert(word)
answer = ""
for word in words:
if tree.search(word) and (
len(word) > len(answer) or len(word) == len(answer) and word < answer
):
answer = word
return answer