????前言
???? 算法题 ????
???? 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程????
???? 提示：本专栏解题 编程语言一律使用 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各字段
依次遍历words,长度为1的为基础加入dic,长度不为1的判断字典是否存在少一长度的值，存在即加入字典
依次遍历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两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！