题目大意：
词典中最长的单词
给出一个字符串数组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"。
注意:
- 所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。words[i]的长度范围为[1,30]。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=720
解题思路分析：
这是一道简单题，但个人认为定义为中等难度会相对适合。本题考到了两个点，字典树以及bfs广度优先搜索。解题时，我们需要先将每个单词放入字典树。然后使用bfs遍历整颗字典树，遍历时，使用bfs对树进行逐层遍历，树每一层上的所有字符串都代表了长度相同的单词，因此在长度相同的情况下，越靠近树左边的单词，相对字典顺序应该更小。向下bfs遍历的条件是，如果当前节点是某一个单词的结尾时才能继续向下，否则无法保证当前线路上的每个单词都是添加一个字母组成。
实现代码：
class Node{ // 字典树节点,每个节点代表一个字母
// 该节点的下一个字母
Node[] children = new Node[26];
// 如果是单词结尾，保存该单词，否则为空
String word;
}
// 定义字典树根节点
Node root = new Node();
public String longestWord(String[] words) {
// 根节点默认单词为空
root.word="";
// 将每一个单词加入字典树
for(String s : words){
Node node = root;
for(int i=0;i<s.length();i++){
int c = s.charAt(i)-'a';
if(node.children[c]==null){
node.children[c] = new Node();
}
node = node.children[c];
}
// 单词结尾时，将该单词保存至当前节点中
node.word=s;
}
// bfs
Queue<Node> q = new LinkedList<>();
// bfs起点
q.offer(root);
// 返回结果
String res = "";
while(q.size()>0){
int size=q.size();
// 当前长度下字典顺序最小的单词
String smallestValid="";
while(size>0){
size--;
Node n = q.poll();
// 记录当前长度下字典顺序最小的单词
if("".equals(smallestValid)) smallestValid = n.word;
Node[] children = n.children;
for(int i=0;i<26;i++){
// 如果子节点为空，或者子节点不是单词结尾，跳过
if(children[i]==null || children[i].word==null) continue;
// 将子节点添加到Queue中（子节点为下一个长度的单词）
q.offer(children[i]);
}
}
// 当前长度遍历完之后，将字典顺序最小的一个保存至返回结果
res = smallestValid;
}
return res;
}本题解法执行时间为11ms。
Runtime: 11 ms, faster than 72.18% of Java online submissions for Longest Word in Dictionary.
Memory Usage: 37.6 MB, less than 81.25% of Java online submissions for Longest Word in Dictionary.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-720-longest-word-in-dictionary-解题思路分析/