LeetCode 720. Longest Word in Dictionary (字典里最长的单词)
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.
Example 1:
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".
Example 2:
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]
.
题目标签:Hash Table
题目给了我们一个 words array,让我们找到里面 最长的word,这个word 是由字典里的其他words 由短到长一步步形成。如果遇到两个同样长度的单词,选一个 字母排序靠前的。
这道题目如果用常规方法做,会比较繁琐,速度也慢。
可以利用sort words,让所有words排序。
遍历words,遇到长度等于 1的 word 或者 这个word 去掉最后一个char 已经存在于 set:
与res 比较 留下 较长的;
把这个word 加入set。
因为是排序后的words,所以遍历顺序会是从a 到z, 从短到长。这样就会留下 最长的符合标准的word。也不用考虑 两个同样长度的 words,因为先选的就是 字母排序靠前的。
Java Solution:
Runtime beats 71.19%
完成日期:11/16/2017
关键词:HashSet,sort
关键点:把word 长度为1 的基础单词 加入 set
class Solution
{
public String longestWord(String[] words)
{
Arrays.sort(words); Set<String> set = new HashSet<>();
String res = ""; for(String word: words)
{
if(word.length() == 1 || set.contains(word.substring(0, word.length() - 1)))
{
res = word.length() > res.length() ? word : res; // keep the longer one
set.add(word);
} } return res;
}
}
参考资料:
https://discuss.leetcode.com/topic/109643/java-c-clean-code
LeetCode 题目列表 - LeetCode Questions List
题目来源:https://leetcode.com/
最新文章
- javascript:正则大全
- 理解JavaScript中的事件轮询
- JavaMail入门第三篇 发送邮件
- linux下使用 Tomcat 的几个坑
- 可拖拽GridView代码解析
- C# 使用ManualResetEvent 进行线程同步
- java中执行js代码
- IntelliJ IDEA 12 创建Web项目 教程 超详细版
- python-Day4-迭代器-yield异步处理--装饰器--斐波那契--递归--二分算法--二维数组旋转90度--正则表达式
- MQTT Client library for C (MQTT客户端C语言库-paho)
- easyui+ajax获取同表关联的数据
- hdu1394 分治 or 线段树
- [HNOI 2011]数矩形
- markdown简易快速的编辑格式(易读易写)
- python3 魔法方法
- CentOS7.4部署Python3+Django+uWSGI+Nginx
- ThinkPHP 框架2.1,2.2和3.0版本开启lite模式导致URL命令执行漏洞
- BiLSTM学习
- [转]Windows7:Visual Studio 2008试用版的评估期已经结束解决方法
- Physical (Raw) Versus Logical Backups
热门文章
- Appium Python API 汇总(中文版)
- Vue实战之插件 sweetalert 的使用
- MySql(五)select排序查询
- python3 操作excel表
- arx升级
- 10JDBC、CURD、XML、XPath
- [UVA11825]Hackers&#39; Crackdown(状压dp)
- 关于ISIS协议 CSNP报文的周期更新理解
- extract a page from a multiple pages pdf on Ubuntu OS
- 洛谷 2966 2966 [USACO09DEC]牛收费路径Cow Toll Paths