【算法千题案例】每日LeetCode打卡——91.词典中最长的单词
【算法千题案例】每日LeetCode打卡——91.词典中最长的单词
呆呆敲代码的小Y
发布于 2021-12-31 08:48:53
发布于 2021-12-31 08:48:53
文章被收录于专栏：呆呆敲代码的小Y 公众号
请添加图片描述
前言
- 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
- 提示：本专栏解题 编程语言一律使用 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两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/12/10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
