- 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/shortest-completing-word/description/
Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate
. Such a word is said to complete the given string licensePlate
Here, for letters we ignore case. For example, "P" on the licensePlate
still matches "p" on the word.
Itis guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.
Thelicense plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate
, but the word "supper" does.
Example 1:
Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.
Example 2:
Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: There are 3 smallest length words that contains the letters "s".
We return the one that occurred first.
Note:
1、 licensePlatewillbeastringwithlengthinrange[1,7].;
2、 licensePlatewillcontaindigits,spaces,orletters(uppercaseorlowercase).;
3、 wordswillhavealengthintherange[10,1000].;
4、 Everywords[i]willconsistoflowercaseletters,andhavelengthinrange[1,15].;
又是一个题目特别长,其实很简单的题,差点就放弃了。。
找出最短的符合licensePlate原则的字符串,如果有多个,那么返回第一个。
licensePlate原则其实特别简单,就是去除掉licensePlate里面的空格和数字,只保留英文字符,并转化为小写。然后再找words中包含这些字符的最短的字符串。
这个题目中licensePlate规则看起来很复杂,其实只保留英文小写字母,然后找匹配就好了。看到一个比较好的方法,是通过Counter来做的,学到了可以使用substract
方法来做减法。这样可以方便的找出words中包含的licensePlate的word。
代码:
import re
from collections import Counter
class Solution(object):
def shortestCompletingWord(self, licensePlate, words):
"""
:type licensePlate: str
:type words: List[str]
:rtype: str
"""
regex = re.compile('[^a-zA-Z]')
license = regex.sub('',licensePlate)
counter1 = Counter(license.lower())
res = ''
for word in words:
if self.count(counter1, word):
if res == '' or len(word) < len(res):
res = word
return res
def count(self, counter1, word):
counter2 = Counter(word)
counter2.subtract(counter1)
return all([c >= 0 for c in counter2.values()])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 二刷,python.
和上面的方法基本一样,可是更容易理解了。
class Solution(object):
def shortestCompletingWord(self, licensePlate, words):
"""
:type licensePlate: str
:type words: List[str]
:rtype: str
"""
subs = "1234567890"
licensePlate = licensePlate.replace(" ", "").lower()
for sub in subs:
licensePlate = licensePlate.replace(sub, "")
res = ""
plateCount = collections.Counter(licensePlate)
for word in words:
match = True
wordCount = collections.Counter(word)
for w, c in plateCount.items():
if c > wordCount[w]:
match = False
if (not res or len(res) > len(word)) and match:
res = word
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我想标记一个字符串,例如 Best Beat Makers,以几乎类似于 NGram 的方式为每个单词生成标记,例如: IN: "Best Beat Makers" OUT: ["Best", "B
这个问题在这里已经有了答案: Is there a way to word-wrap long words in a div? (6 个答案) 关闭 7 年前。
我想编写一个 Python 代码来检查字符串是否包含类似于以下内容的内容: 'word.Word' => 将其替换为 'word.\nWord'。 smallLetter.capitalLetter
我想编写一个 Python 代码来检查字符串是否包含类似于以下内容的内容: 'word.Word' => 将其替换为 'word.\nWord'。 smallLetter.capitalLetter
我有以下正则表达式: ^--([\w|-]+) 我想匹配 --word --no-word 但不是: ---word ----word 最佳答案 将表情更改为 ^--(\w[-\w]*) 这需要在两个
在我的加载项中,我需要为每个打开的文档创建一个任务 Pane 。在加载项的启动方法中,我订阅了 ApplicationEvents4_Event.NewDocument 和 Application.D
我使用 word javascript api 开发了一个 word 插件。我的文档 .docx 文件在服务器上,我需要在加载项中单击按钮打开该 .docx 文档作为新的 Word 文档。 请指导我如
我需要在某个地方修复一些 CSS,因为我的文本没有环绕,如果它是一个非常长的单词,它会无限期地继续下去。 在大多数情况下,我在我的 CSS 文件中尝试了 word-wrap: break-word;
这个问题在这里已经有了答案: What is the difference between "word-break: break-all" versus "word-wrap: break-word
这个问题在这里已经有了答案: What is the differect between word-wrap and overflow-wrap? [duplicate] (1 个回答) Is t
问题详细描述如下: 给定两个单词(beginWord 和 endWord)和字典的单词列表,找出是否存在从 beginWord 到 endWord 的转换序列,这样: 一次只能更改一个字母 每个转换后
我以前没有使用过邮件合并字段,我发现的所有内容都要求您在能够插入合并字段之前选择一个数据源。我想要做的就是将字段放在 word 文档上,并且在代码使用它之前不要将其合并。我基本上是在创建文档模板。这在
将此代码放置在ThisDocument_Startup之外的Word文档级VSTO解决方案中的某个位置(创建带单击事件的功能区按钮): int zero = 0; int divideByZero =
有没有办法在没有加载项的情况下启动 MS Word(仅此实例)?我只能找到一种方法来完全禁用加载项。 最佳答案 来自Word command line switches documentation ,
有没有办法在没有加载项的情况下启动 MS Word(仅此实例)?我只找到一种方法来完全禁用加载项。 最佳答案 来自Word command line switches documentation ,您
当使用 URI 方案从网页上托管的 word 模板打开新文档时不起作用。 https://msdn.microsoft.com/en-us/library/office/dn906146.aspx 这
我的问题: overflow-wrap: break-word 和 word-break: break-word 有区别吗? 非重复: 这里有一些现有的问题,乍一看可能是重复的,但实际上不是。 Wha
我希望使用 WordNet 从一组基本术语中寻找相似术语的集合。 例如,单词'discouraged' - 潜在的同义词可能是:daunted, glum, deterred, pessimistic
部署 Word Add in 时,发布没有错误。复制文件后出现以下错误。 我没有太多事情要做。这是堆栈跟踪。 ************** Exception Text **************
我需要一个 Java 正则表达式来匹配除某个单词之外的任何单词,同时包含另一个单词。 例如字符串中不能包含Apple,但必须有Peach。 Apple and Peach - Not match Pe
我是一名优秀的程序员,十分优秀!