LeetCode 题解工作台
词典中最长的单词
给出一个字符串数组 words 组成的一本英语词典。返回能够通过 words 中其它单词逐步添加一个字母来构造得到的 words 中最长的单词。 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。 请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。 …
5
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用字典树来存储所有的单词，然后遍历所有的单词，判断当前单词是否可以由字典树中的其他单词逐步添加一个字母组成，找出满足条件的最长的，且字典序最小的单词。 时间复杂度 ，空间复杂度 ，其中 是所有单词的长度之和。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给出一个字符串数组 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 <= 10001 <= words[i].length <= 30- 所有输入的字符串
words[i]都只包含小写字母。
解题思路
方法一：字典树
我们可以使用字典树来存储所有的单词，然后遍历所有的单词，判断当前单词是否可以由字典树中的其他单词逐步添加一个字母组成，找出满足条件的最长的，且字典序最小的单词。
时间复杂度 ，空间复杂度 ，其中 是所有单词的长度之和。
class Trie:
def __init__(self):
self.children: List[Optional[Trie]] = [None] * 26
self.is_end = False
def insert(self, w: str):
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, w: str) -> bool:
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
return False
node = node.children[idx]
if not node.is_end:
return False
return True
class Solution:
def longestWord(self, words: List[str]) -> str:
trie = Trie()
for w in words:
trie.insert(w)
ans = ""
for w in words:
if trie.search(w) and (
len(ans) < len(w) or (len(ans) == len(w) and ans > w)
):
ans = w
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(∑ w_i) due to iterating over all words and checking their prefixes, and space complexity is O(∑ w_i) because of storing words in a Set for fast lookups. |
| 空间 | O(\sum w_i) |
面试官常问的追问
外企场景- question_mark
Evaluate whether the candidate efficiently uses hash sets for prefix checking.
- question_mark
Assess how well the candidate handles lexicographical order when there are multiple valid longest words.
- question_mark
Check if the candidate optimizes for time and space when validating word prefixes.
常见陷阱
外企场景- error
Failing to use a Set to quickly check word prefixes can result in slower solutions.
- error
Not handling multiple valid words with the same length but different lexicographical orders correctly.
- error
Overlooking edge cases where no valid word can be built from the dictionary.
进阶变体
外企场景- arrow_right_alt
Consider cases where the input list contains a mix of short and long words.
- arrow_right_alt
Test the solution against a dictionary with words having the same prefixes but different lengths.
- arrow_right_alt
Evaluate performance when all words in the dictionary are valid and can be built from each other.