leetcode 720. Longest Word in Dictionary
2024-10-21 12:52:49
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]
.
排序+set解法
class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
# use greey algo
# find the most length word that can be built one character at a time by other words in words
words_set = set([""])
words.sort()
ans = ""
for word in words:
if word[:-1] in words_set:
if len(word) > len(ans):
ans = word
words_set.add(word)
return ans
或者是trie:
class Node(object):
def __init__(self, val=""):
self.val = val
self.subs = collections.defaultdict(Node) class Trie(object):
def __init__(self):
self.root = Node("") def insert(self, s):
node = self.root
for c in s:
node = node.subs[c]
node.val = s def longest_word(self):
self.ans = ""
def dfs(node):
for k, n in node.subs.items():
if n.val:
if len(n.val)>len(self.ans) or (len(n.val)==len(self.ans) and n.val<self.ans):
self.ans = n.val
dfs(n)
dfs(self.root)
return self.ans class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
trie = Trie()
for word in words:
trie.insert(word)
return trie.longest_word()
最新文章
- Ubuntu 16.04 下安装Firefox的Flash插件
- ABBYY把pdf转换成word的方法
- java应用程序利用Exe4j打包exe文件
- [辛酸历程]在Mac中使用Python获取屏幕截图
- VS2010使用Qt库
- [WPF疑难]Hide me! not close
- ScaleAnimation类:尺寸变化动画类
- jquery插件之DataTables 参数介绍
- Github 开源:使用 .NET WinForm 开发所见即所得的 IDE 开发环境(Sheng.Winform.IDE)【2.源代码简要说明】
- 分布式架构ActiveMQ的安装与使用(单节点)
- AQS 框架之 Unsafe 源码详解
- React知识杂烩(持续更新)
- 吴恩达机器学习笔记2-代价函数I(cost function)
- -Dmaven.multiModuleProjectDirectory system property is not set.
- linux进阶命令第一天
- epoll的ET和LT模式
- 记一次无法正常本地登陆Linux服务器(确定密码正确)
- 解决chrome无法启用印象笔记-剪藏功能
- Java并发(二)-实现同步
- poj1284 Primitive Roots
热门文章
- .net操作xml文件(新增.修改,删除,读取) 转
- 『NiFi 学习之路』把握 —— 架构及主要部件
- deeplenrnig学习笔记——什么是特征
- oracle同一个库上面,不同用户相互赋予权限
- 三年半Java后端面试经历
- mysql对数据库的备份和还原
- 2019 google kickstart round A
- minSdk(API 21) >; deviceSdk(API 17)解决
- MySQL MERGE存储引擎 简介及用法
- spring-security权限控制详解