文档章节

字典中的最长单词 Longest Word in Dictionary

叶枫啦啦
 叶枫啦啦
发布于 2018/01/17 10:05
字数 629
阅读 23
收藏 0

问题:

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

  • All the strings in the input will only contain lowercase letters.
  • The length of words will be in the range [1, 1000].
  • The length of words[i] will be in the range [1, 30].

解决:

【题意】给定一个字典,是个字符串数组,从单个字符开始拼,返回最长能组成单词,注意中间生成的字符串也要在字典中存在,而且当组成的单词长度相等时,返回字母顺序小的那个。

① 先将单词按照字典序排序,为了快速的查找某个单词是否在字典中存在,将字典中的单词存储到set集合中。

class Solution { //42ms
    public String longestWord(String[] words) {
        Arrays.sort(words);//按照字典序排序
        Set<String> set = new HashSet<>();//用于存储字典中已经存在的字符
        String res = "";
        for (String word : words){
            if (word.length() == 1 || set.contains(word.substring(0,word.length() - 1))){
                res = word.length() > res.length() ? word : res;
                set.add(word);
            }
        }
        return res;
    }
}

② 使用前缀树,bfs查找。

class Solution { //20ms
    class TrieNode{
        TrieNode[] children;
        boolean isWord;
        String word;
        public TrieNode(){
            children = new TrieNode[26];
        }
    }
    class Trie{
        private TrieNode root;
        public Trie(){
            root = new TrieNode();
        }
        public void insert(String word){
            TrieNode node = root;
            for (int i = 0;i < word.length();i ++){
                int index = word.charAt(i) - 'a';
                if (node.children[index] == null){
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isWord = true;
            node.word = word;
        }
        public String findLongestWord(){
            String res = null;
            Queue<TrieNode> queue = new LinkedList<>();
            queue.offer(root);
            while(! queue.isEmpty()){
                int count = queue.size();
                for (int i = 0;i < count;i ++){
                    TrieNode node = queue.poll();
                    for (int j = 25;j >= 0;j --){
                        if (node.children[j] != null && node.children[j].isWord){
                            res = node.children[j].word;
                            queue.offer(node.children[j]);
                        }
                    }
                }
            }
            return res;
        }
    }
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String word : words){
            trie.insert(word);
        }
        return trie.findLongestWord();
    }
}

③ 前缀树+dfs查找

class Solution { //18ms
    class TrieNode{
       TrieNode[] children;
       String word;
       public TrieNode(){
           children = new TrieNode[26];
       }
    }
    TrieNode root = new TrieNode();
    public String longestWord(String[] words){
        root.word = "";
        for (String word : words){
            insert(word);
        }
        TrieNode cur = root;
        return dfs(cur);
    }
    public void insert(String word){
        TrieNode cur = root;
        for (char c : word.toCharArray()){
            int index = c - 'a';
            if (cur.children[index] == null){
                cur.children[index] = new TrieNode();
            }
            cur = cur.children[index];
        }
        cur.word = word;
    }
    public String dfs(TrieNode cur){
        String res = cur.word;
        for (int i = 0;i < 26;i ++){
            if (cur.children[i] != null && cur.children[i].word != null){
                String tmp = dfs(cur.children[i]);
                if (tmp.length() > res.length()){
                    res = tmp;
                }
            }
        }
        return res;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
字典中最长的一个单词,可以通过给定单词通过删除某些字符得到

Longest Word in Dictionary through Deleting 问题: Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characte......

叶枫啦啦
2018/01/09
47
0
Google 面试题 | 字典里面的最长单词

专栏 | 九章算法 网址 | http://www.jiuzhang.com 三角形分割线 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案...

2018/02/10
0
0
Leetcode【939、1048】

问题描述:【Hash Table】939. Minimum Area Rectangle 解题思路: 最小面积矩形。给一个坐标列表,计算这些坐标可以组成的最小矩形面积,其中矩形平行于 x 轴和 y 轴。 这是一道 Google 面试...

牛奶芝麻
07/29
0
0
Q720 Longest Word in Dictionary

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is m......

牛奶芝麻
2018/08/11
0
0
Leetcode 【524、767、1053、1079】

问题描述:【Two Pointers】524. Longest Word in Dictionary through Deleting 解题思路: 这道题是给一个字符串s和一个单词数组,找到数组里面最长的单词,该单词可以通过删除s的某些字符来...

牛奶芝麻
06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么?老程序员申请加薪至30K遭拒愤然辞职,公司转眼花35K招新

身在职场,经常会暗自打听同事工资,尤其是得知身边新入职同事的工资居然比自己高,还高出一大截时,心里自然很不平衡,一心想要离职。 那么,为什么公司宁愿花高价招聘新员工也不愿意给老员...

Java技术剑
13分钟前
3
0
云桌面到底是什么,企业该用云桌面吗

随着云计算和大数据时代的到来,当前企业里讨论最多的话题之一就是:企业到底要不要用云桌面这个话题的,有的人说企业应该使用云桌面的,因为可以降低使用成本和简化运维管理,同时也有的人说...

GZASD
18分钟前
3
0
技术分享 | gh-ost 原理剖析

作者简介: 杨奇龙,网名“北在南方”,7年DBA老兵,目前任职于杭州有赞科技DBA,主要负责数据库架构设计和运维平台开发工作,擅长数据库性能调优、故障诊断。 一、简介 上一篇文章(gh-ost ...

爱可生
21分钟前
5
0
手机短信删除了怎么恢复?几个方法就能恢复

  手机短信删除了怎么恢复?前几天有个小伙伴收到了一条来着面试的通知,这个面试对他很重要,但是可气的是刚好在清理手机里面的垃圾短信,然后收到了短信之后又被删除了,却又不知道该怎么...

科技第六人
36分钟前
5
0
浅谈Builder建造者模式

一、前言 Builder建造者模式和模板模式非常像,但是也有区别,模板模式中父类对子类中的实现进行操作,在父类之中进行一件事情的处理,但是在Builder模式之中,父类和子类都不用关心怎么处理...

青衣霓裳
40分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部