题目大意:
词典中最长的单词
给出一个字符串数组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-解题思路分析/