- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/longest-word-in-dictionary/description/open in new window
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.
Ifthere 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:
1、 Allthestringsintheinputwillonlycontainlowercaseletters.;
2、 Thelengthofwordswillbeintherange[1,1000].;
3、 Thelengthofwords[i]willbeintherange[1,30].;
找出字符串数组中最长的一个字符串,这个字符串的所有前缀都能在这个数组中找到。如果存在多个长度相等的满足要求的字符串,返回字母序最小的那个。
对于每个字符串都去查找它的所有前缀是不是都在数组中,如果是的话,然后比较是不是最长的、如果同样长度的话是不是字母序更小。
class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
wset = set(words)
res = ""
for w in words:
isIn = True
for i in range(1, len(w)):
if w[:i] not in wset:
isIn = False
break
if isIn:
if not res or len(w) > len(res):
res = w
elif len(w) == len(res) and res > w:
res = w
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
巧妙用了set(),判断每个单词的除去倒数第一个字母是否在set里,用一个变量保存最长的单词。
用判断新单词是否比最长单词更长的方式完成两个需求:1.找出最长;2.同样最长的情况下,保留字母序最小的。这样做的前提是先对words进行排序。
class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
words.sort()
res = set([''])
longestWord = ''
for word in words:
if word[:-1] in res:
res.add(word)
if len(word) > len(longestWord):
longestWord = word
return longestWord
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在用 Python (2.6) 编写一个应用程序,需要我使用字典作为数据存储。 我很好奇拥有一个大字典是否更节省内存,或者将其分解为许多(很多)较小的字典,然后拥有一个包含对所有较小字典的引用的“
Convert this [ "Cat" : ["A" : 1, "B": 2], "Mat" : ["C" : 3, "D": 4] ] Into [ "A" : 1,
有什么很酷的快速方法可以让两个字典创建第三个字典,以内连接方式将第一个字典的键映射到第二个字典的值? Dictionary dic1 = new Dictionary {{a1,b1},{a2,b2}
我希望将字典相互嵌套,以便容纳 block 的 xy 坐标。所以我会 IDictionary, IDictionary> 键 Dictionary 包含列、行组合,而值 Dictionary 包含 x
在 C# 中,我需要将数据保存在字典对象中,如下所示: Dictionary> MyDict = new Dictionary>(); 现在我意识到,在某些情况下我需要一些其他(不是字典类的)
第一个Dictionary就像 Dictionary ParentDict = new Dictionary(); ParentDict.Add("A_1", "1")
我似乎无法理解这个问题。我需要使用 LINQ 按内部字典的值对字典进行排序。有什么想法吗? 最佳答案 你的意思是你想要所有的值,按内部值排序? from outerPair in outer from
我想建模一个模式,其中响应是字典: { 'id1': { 'type': 'type1', 'active': true, }, 'id2': { 'type':
我有以下代码要添加或更新(如果已经存在)dict()-dict 中的值: if id not in self.steps: self.steps[ id ] = step else:
我有一个包含字典的 Swift 字典,我想使用存储的属性来访问键值: var json = [NSObject:AnyObject]() var title: String { get
我想创建一个 Dictionary>结构,我想提供一个 IEqualityComparer在包含 APerson 的second 字典中作为关键 如果我只有内部字典,那就是 var f = new D
我有一个集合,其中包含如下文档:文档 1: { "company": "ABC" "application": { "app-1": {"earning_from_src_A": 50,
我正在快速学习。 我发现 dictionary 就像 hash 用于 PHP 或其他一些语言。 那我怎么制作dictionary的dictionary呢?? 我有这样的数据 key:J name:jh
这个问题在这里已经有了答案: Explode a dict - Get all combinations of the values in a dictionary (2 个答案) 关闭 5 个月前
我是编程新手,所以如果我的问题看起来很愚蠢,我很抱歉。我想问一下有没有办法从 Multi.Dictionary 返回key当我有值(value)? 这是我的代码: Dim myDict Set myD
我试图找出标准 Ada 库是否配备了“字典”类型(我的意思是:一种以 格式存储值的数据结构,我可以从中检索 value 使用相应的唯一 key)。 这样的数据结构存在吗?如果是这样,有人可以提供一个
我究竟做错了什么?根据我的测试,objDic.exists 永远不会给出 False! dim objDic set objDic = createobject("scripting.
我想创建一个复合类型,其中包含一个字典作为其命名字段之一。但是明显的语法不起作用。我敢肯定有一些我不明白的基本原理。下面是一个例子: type myType x::Dict() end Jul
julia> hotcell2vocab = Dict([(cell, i-1+vocab_start) for (i,cell) in enumerate(h
我有一个简单的问题:我对 Dictionary.Value 集合进行了很多次迭代,这让我很烦,我必须调用 .ToList() 然后才能调用 .ForEach(),因为它似乎没有可枚举的Dictiona
我是一名优秀的程序员,十分优秀!