【LeetCode】30. Substring with Concatenation of All Words
2024-08-26 01:49:22
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9]
.
(order does not matter).
题意:找出所给列表words中的单词相接的子句在s中出现的索引。
注意:words中的单词可能重复出现
思路:1.建立一个字典wdict,统计words中所有单词的个数
2.判断s中所有可能的子句是否符合要求
1)判断字据中每个单词是否出现在wdict中,没有的话,此子句不符合要求
2)子句符合要求的话,加入新的属于子句的字典,如果子句中某个单词出现的次数超过wdict中这个单词出现的个数,此子句不符合要求
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
res = []
length = len(words[0])
num = len(words)
l = length*num
lens = len(s)
wdict = {}
sset = set()#建立集合,收集所有已经符合条件的字句,减少判断次数
for word in words:
wdict[word] = 1+(wdict[word] if word in wdict else 0)
first_char = set(w[0] for w in words)#建立集合收集所有单词中的第一个字母,减少isRequired的次数
for i in range(lens-l+1):
if s[i] in first_char:
tmp = s[i:i+l]
if tmp in sset or self.isRequired(tmp,wdict,length):
sset.add(tmp)
res.append(i)
return res
def isRequired(self,s,wdict,length):
comp = {}
i = 0
while(i<len(s)-length+1):
tmp = s[i:i+length]
if tmp not in wdict:
return False
else:
comp[tmp] = 1+(comp[tmp] if tmp in comp else 0)
if comp[tmp]>wdict[tmp]:
return False
i += length
return True
最新文章
- oracle db link的查看创建与删除
- BFC and Haslayout
- Nodejs学习笔记(十一)--- 数据采集器示例(request和cheerio)
- GitHub 操作流程示例
- Oracle数据库表结构导出
- 如何用JAVA生成注册序列号
- cf D George and Interesting Graph
- [HMLY]5.模仿喜马拉雅 FM
- php的memcache和memcached扩展区别【转载】
- 2016.02.01日,UdoOS系统项目正式开通了
- ROS(indigo)机器人操作系统学习资料和常用功能包汇总整理(ubuntu14.04LTS)
- HTML条件注释
- intent--Activity之间数据传递之Intent数据传递
- 6.form表单四种提交方式
- 利用Warensoft Stock Service编写高频交易软件--DEMO
- Servlet实例开发---学生管理系统
- Mac下安装Docker
- 微信小程序转发商品的详情页 + 转发功能(传参)
- angularjs中响应回车事件
- 更新表中数据可以使用join