X

LEETCODE 720. Longest Word in Dictionary 解题思路分析

题目大意:

词典中最长的单词

给出一个字符串数组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-解题思路分析/
Categories: leetcode
kwantong: