【算法千题案例】每日LeetCode打卡——91.词典中最长的单词

📢前言 🚀 算法题 🚀

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
• 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
• 🌲 今天是力扣算法题持续打卡第91天🎈！

🚀 算法题 🚀 🌲原题样例：词典中最长的单词

给出一个字符串数组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]。

🌻C#方法：排序遍历

先排序，定义的一个字典dic用来存放words各字段

1. 依次遍历words,长度为1的为基础加入dic,长度不为1的判断字典是否存在少一长度的值，存在即加入字典
2. 依次遍历dic寻找最长string

代码：

public class Solution {
    public string LongestWord(string[] words) {
        Dictionary dic = new Dictionary();
            Array.Sort(words);
            for (int i = 0; i len)
                {
                    len = item.Value;
                    res = item.Key;
                }
            }
            return res;
    }
}

执行结果

通过
执行用时：124 ms，在所有 C# 提交中击败了100.00%的用户
内存消耗：45.9 MB，在所有 C# 提交中击败了43.90%的用户

🌻Java 方法：暴力法

思路解析 对于每个单词，我们可以检查它的全部前缀是否存在，可以通过 Set 数据结构来加快查找

• 当我们找到一个单词它的长度更长且它的全部前缀都存在，我们将更改答案。
• 或者，我们可以事先将单词排序，这样当我们找到一个符合条件的单词就可以认定它是答案。

代码：

class Solution {
    public String longestWord(String[] words) {
        Set wordset = new HashSet();
        for (String word: words) wordset.add(word);
        Arrays.sort(words, (a, b) -> a.length() == b.length()
                    ? a.compareTo(b) : b.length() - a.length());
        for (String word: words) {
            boolean good = true;
            for (int k = 1; k