C#LeetCode刷题之#720-词典中最长的单词(Longest Word in Dictionary)
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4120 访问。
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词,该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案,则返回答案中字典序最小的单词。
若无答案,则返回空字符串。
输入: words = ["w","wo","wor","worl", "world"]
输出: "world"
解释: 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
输入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出: "apple"
解释: "apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
注意:
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.
If there is no answer, return the empty string.
Input: words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Note:
All the strings in the input will only contain lowercase letters.
The length of words will be in the range [1, 1000].
The length of words[i] will be in the range [1, 30].
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4120 访问。
public class Program {
public static void Main(string[] args) {
var words = new string[] { "a", "banana", "app", "appl", "ap", "apply", "apple" };
var res = LongestWord(words);
Console.WriteLine(res);
Console.ReadKey();
}
private static string LongestWord(string[] words) {
var wordsSet = new HashSet<string>();
var resultSet = new HashSet<string>();
Array.Sort(words);
for(var i = 0; i < words.Length; i++) {
wordsSet.Add(words[i]);
}
for(var i = words.Length - 1; i >= 0; i--) {
if(IsCompleteWord(words[i], wordsSet)) {
resultSet.Add(words[i]);
}
}
var list = resultSet.OrderByDescending(r => r.Length).ToList();
return list.Where(r => r.Length == list[0].Length).Min();
}
private static bool IsCompleteWord(string word, HashSet<string> wordsSet) {
for(var i = 0; i < word.Length; i++) {
if(!wordsSet.Contains(word.Substring(0, i + 1))) return false;
}
return true;
}
}
以上给出1种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/4120 访问。
apple
分析:
设单词的最大长度为m,那么以上算法的时间复杂度应为: 。
最新文章
- 如何修改Hadoop的默认日志级别,还真是麻烦
- 第K大数
- Mysql --分区(4)List分区
- 转 PHP在JVM上的实现JPHP
- XP系统电脑带安卓手机上网教程(无需adhoc补丁)
- MFC记录
- java中String s=";abc";及String s=new String(";abc";)详解
- poj1511/zoj2008 Invitation Cards(最短路模板题)
- js 环形链表
- 【测试环境】cywin的简单介绍
- 强大的Mockito测试框架(转)
- 新秀发挥云17号:RHEL改变以太网地址克隆虚拟机后,
- ORM查询语言OQL
- LeetCode第七天
- laravel5.5 延时队列的使用
- Helm包管理工具(简介、安装、方法)
- linux下mysql 配置
- Modbus库开发笔记:Modbus ASCII Master开发
- Java多线程:volatile 关键字
- C++中的return和exit区别