题目来源:
https://leetcode.com/problems/word-break-ii/
题意分析:
给定一个字符串s和一个字典dict(set),将所有将s有字典dict组成的结果输出。比如s = "catsanddog"
,
dict = ["cat", "cats", "and", "sand", "dog"]
.那么结果是["cats and dog", "cat sand dog"]。
题目思路:
我们将问题细化,如果s[:i]在字典dict里面,那么结果就是s[:i]和 solve(s[i + 1:],dict)的笛卡尔乘积。如果直接实现,那么时间复杂度较高,所以这里用动态规划的思想,判断一个字符串是否可以有字典组成。
代码(python):
class Solution(object):
def isp(self,s,dict):
dp = [False for i in range(len(s) + 1)]
dp[0] = True
for i in range(1,len(s) + 1):
for j in range(0,i):
if dp[j] and s[j:i] in dict:
dp[i] = True
return dp[len(s)]
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
ans,tmp = [],""
if s in wordDict:
ans.append(s)
for i in range(len(s)):
tmp += s[i]
if tmp in wordDict:
if self.isp(s[i + 1:],wordDict):
t = self.wordBreak(s[i+1:],wordDict)
for j in t:
ans.append(tmp + " " + j)
return ans
[LeetCode]题解(python):140-Word Break II的更多相关文章
-
LeetCode笔记:140. Word Break II
题目描述 给定一个非空的字符串s,一个非空的字符串list作为字典.通过在s中添加空格可以将s变为由list中的word表示的句子,要求返回所有可能组成的句子.设定list中的word不重复,且每一个 ...
-
leetcode 139. Word Break 、140. Word Break II
139. Word Break 字符串能否通过划分成词典中的一个或多个单词. 使用动态规划,dp[i]表示当前以第i个位置(在字符串中实际上是i-1)结尾的字符串能否划分成词典中的单词. j表示的是以 ...
-
140. Word Break II(hard)
欢迎fork and star:Nowcoder-Repository-github 140. Word Break II 题目: Given a non-empty string s and a d ...
-
【LeetCode】140. Word Break II
Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a senten ...
-
【LeetCode】140. Word Break II 解题报告(Python & C++)
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 递归求解 日期 题目地址:https://leetc ...
-
[LeetCode] 140. Word Break II 单词拆分II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add space ...
-
140. Word Break II
题目: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where e ...
-
139. Word Break 以及 140.Word Break II
139. Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty ...
-
leetcode 140. Word Break II ----- java
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each ...
-
Java for LeetCode 140 Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each ...
随机推荐
-
UVA 11817 Tunnelling the Earth --球面距离公式
题意: 给出两点的经纬度,求两点的球面距离与直线距离之差. 解法: 我们先算出球面距离,然后可以根据球面距离算出直线距离. 球面距离公式: R*acos(sin(W1)*sin(W2)+cos(W1) ...
-
『转载』C# winform 中dataGridView的重绘(进度条,虚线,单元格合并等)
原文转载自:http://hi.baidu.com/suming/item/81e45b1ab9b4585f2a3e2243 最近比较浅的研究了一下dataGridView的重绘,发现里面还是有很多东 ...
-
oracle Instance status: READY–lsnrctl status|start|stop
监听器启动,并不一定会认识数据库实例,启动监听器,请判别相关实例是否 READY [oracle@redhat4 ~]$ lsnrctl status LSNRCTL for Linux: Versi ...
-
355. Design Twitter
二刷尝试了别的办法,用MAP代表关注列表. 然后不初始化,但是只要有用户被使用,而他又不在MAP里,就把他加进去,然后让他关注自己.. 但是这样做超时了. 问题在于这个题解法太多,有很多不同的情况. ...
-
Ruby自学笔记(一)— 基本概况
之前一直想要多看看RESTful Service相关的东西,找到一本相关的书,但是里面的代码都是用Ruby写的,虽然知道编程语言都是类似的,但是看到一些陌生的语法,还是有些摸不着头脑,所以最近终于下定 ...
-
js实现网页收藏功能,动态添加删除网址
<html> <head> <title> 动态添加删除网址 </title> <meta charset="utf-8"&g ...
-
laytpl--前端数据绑定
发现一枚前端数据绑定导弹:laytpl,官网:http://www.layui.com/laytpl/ 为了不用angularJS等较为重量级的,和繁琐的配置,所以就用了laytpl,可以配合JQ使用 ...
-
Java 关于路径
在eclipse中如果没有指名文件的路径的话,系统默认是与src同一级别的目录路径!
-
vue cli搭建的vue项目 不小心开了eslint 一直报黄色的警告
报错必须处理,警告也忍不了,发现在bulid -webpack.base.config.js 里找到 const createLintingRule = () => ({ /*test: /\. ...
-
VC++:制作一个控件注册的小工具
在平时的工作中,时常需要注册与反注册ActiveX控件,有时需要判断控件是否已经注册. 所以通过查找资料编写了一个控件注册的小工具,欢迎学习交流,不当之处请多多交流. 先直接上图: 主要代码: ...