题目
#
- 给出一个字符串数组
words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
- 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
- 例如:
输入：words = ["w","wo","wor","worl", "world"]
输出："world"
解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
思路
#
排序+哈希
#
前缀树
#
代码
#
排序+哈希
#
class Solution {
public String longestWord(String[] words) {
Arrays.sort(words);
Set<String> set = new HashSet<>();
set.add("");
String ans = "";
for (String word: words) {
if (set.contains(word.substring(0, word.length()-1))) {
set.add(word);
if (ans.length() < word.length()) ans = word;
}
}
return ans;
}
}
前缀树
#
致谢
#
微扰理论
宫水三叶