友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
720. 词典中最长的单词
给出一个字符串数组 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]都只包含小写字母。
思路分析
先将每个单词都插入前缀树，然后再逐个判定每个单词是否在前缀树。这里要注意：判定是否在前缀树中，还要判定每个字母都要是单词结尾才行。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-26 22:50:40
*/
public String longestWord(String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
String result = "";
for (String word : words) {
if (trie.search(word)) {
if (word.length() > result.length()
|| (word.length() == result.length() && word.compareTo(result) < 0)) {
result = word;
}
}
}
return result;
}
public static class Trie {
private Trie[] children = new Trie[26];
private boolean isWord = false;
public void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isWord = true;
}
public boolean search(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null || !node.children[index].isWord) {
return false;
}
node = node.children[index];
}
return node != null && node.isWord;
}
}