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

@TOC

📢前言

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 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<string, int> dic = new Dictionary<string, int>();
            Array.Sort(words);
            for (int i = 0; i < words.Length; i++)
            {
                if (words[i].Length==1)
                {
                    if(!dic.ContainsKey(words[i])){
                        dic.Add(words[i], 1);
                    }  
                    
                }
                else 
                {
                    if (dic.ContainsKey(words[i].Substring(0,words[i].Length-1))&&!dic.ContainsKey(words[i]))
                    {
                        //dic.Remove(words[i].Substring(0, words[i].Length - 1));
                        dic.Add(words[i], words[i].Length);
                    }
                }
            }
            string res = "";
            int len = 0;
            foreach (var item in dic)
            {
                if (item.Value>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<String> 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 < word.length(); ++k) {
                if (!wordset.contains(word.substring(0, k))) {
                    good = false;
                    break;
                }
            }
            if (good) return word;
        }

        return "";
    }
}

执行结果

通过
执行用时：13 ms，在所有 Java  提交中击败了66.41%的用户
内存消耗：38.3 MB，在所有 Java 提交中击败了94.50%的用户

复杂度分析

时间复杂度：O( n )
空间复杂度：O(1) 

💬总结

• 今天是力扣算法题打卡的第九十一天！
• 文章采用 C#和 Java 两种编程语言进行解题
• 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
• 那今天的算法题分享到此结束啦，明天再见！