本文共 1662 字，大约阅读时间需要 5 分钟。

领扣LintCode算法问题答案-1071. 词典中最长的单词

1071. 词典中最长的单词

描述

给出一系列字符串单词表示一个英语词典，找到字典中最长的单词，这些单词可以通过字典中的其他单词每次增加一个字母构成。 如果有多个可能的答案，则返回字典顺序最小的那个。

如果没有答案，则返回空字符串。

1. 输入中的所有字符串只包含小写字母。
2. words 的长度范围为 [1, 1000].
3. words[i] 的长度范围为 [1, 30].

样例 1：

输入: words = ["w","wo","wor","worl", "world"]输出: "world"解释: 单词"world" 可以通过 "w", "wo", "wor", and "worl"每次增加一个字母构成。

样例 2：

输入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]输出: "apple"解释: 单词"apply" 和 "apple" 都能够通过字典里的其他单词构成。 但是 "apple" 的字典序比 “apply”小。

题解

public class Solution {
       /**     * @param words: a list of strings     * @return: the longest word in words that can be built one character at a time by other words in words     */    public String longestWord(String[] words) {
           // Write your code here        Arrays.sort(words, new Comparator
   
    () {
               @Override            public int compare(String o1, String o2) {
                   int c = o2.length() - o1.length();                if (c == 0) {
                       c = o1.compareTo(o2);                }                return c;            }        });        Set
    
      set = new HashSet<>();        Collections.addAll(set, words);        for (String word : words) {
               String tempWord = word;            boolean found = true;            while(tempWord.length() > 1                    && found) {
                   tempWord = tempWord.substring(0, tempWord.length() - 1);                found = set.contains(tempWord);            }            if (found) {
                   return word;            }        }        return "";    }}
    
   

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。

欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

转载地址：https://le-yi.blog.csdn.net/article/details/108809215 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！