[LeetCode]题解(python):140-Word Break II

时间:2021-07-08 17:42:14

题目来源:

  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的更多相关文章

  1. LeetCode笔记:140. Word Break II

    题目描述 给定一个非空的字符串s,一个非空的字符串list作为字典.通过在s中添加空格可以将s变为由list中的word表示的句子,要求返回所有可能组成的句子.设定list中的word不重复,且每一个 ...

  2. leetcode 139. Word Break 、140. Word Break II

    139. Word Break 字符串能否通过划分成词典中的一个或多个单词. 使用动态规划,dp[i]表示当前以第i个位置(在字符串中实际上是i-1)结尾的字符串能否划分成词典中的单词. j表示的是以 ...

  3. 140. Word Break II(hard)

    欢迎fork and star:Nowcoder-Repository-github 140. Word Break II 题目: Given a non-empty string s and a d ...

  4. 【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 ...

  5. 【LeetCode】140. Word Break II 解题报告(Python & C++)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 递归求解 日期 题目地址:https://leetc ...

  6. [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 ...

  7. 140. Word Break II

    题目: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where e ...

  8. 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  ...

  9. 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 ...

  10. 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 ...

随机推荐

  1. UVA 11817 Tunnelling the Earth --球面距离公式

    题意: 给出两点的经纬度,求两点的球面距离与直线距离之差. 解法: 我们先算出球面距离,然后可以根据球面距离算出直线距离. 球面距离公式: R*acos(sin(W1)*sin(W2)+cos(W1) ...

  2. 『转载』C# winform 中dataGridView的重绘(进度条,虚线,单元格合并等)

    原文转载自:http://hi.baidu.com/suming/item/81e45b1ab9b4585f2a3e2243 最近比较浅的研究了一下dataGridView的重绘,发现里面还是有很多东 ...

  3. oracle Instance status: READY–lsnrctl status|start|stop

    监听器启动,并不一定会认识数据库实例,启动监听器,请判别相关实例是否 READY [oracle@redhat4 ~]$ lsnrctl status LSNRCTL for Linux: Versi ...

  4. 355. Design Twitter

    二刷尝试了别的办法,用MAP代表关注列表. 然后不初始化,但是只要有用户被使用,而他又不在MAP里,就把他加进去,然后让他关注自己.. 但是这样做超时了. 问题在于这个题解法太多,有很多不同的情况. ...

  5. Ruby自学笔记(一)— 基本概况

    之前一直想要多看看RESTful Service相关的东西,找到一本相关的书,但是里面的代码都是用Ruby写的,虽然知道编程语言都是类似的,但是看到一些陌生的语法,还是有些摸不着头脑,所以最近终于下定 ...

  6. js实现网页收藏功能,动态添加删除网址

    <html> <head> <title> 动态添加删除网址 </title> <meta charset="utf-8"&g ...

  7. laytpl--前端数据绑定

    发现一枚前端数据绑定导弹:laytpl,官网:http://www.layui.com/laytpl/ 为了不用angularJS等较为重量级的,和繁琐的配置,所以就用了laytpl,可以配合JQ使用 ...

  8. Java 关于路径

    在eclipse中如果没有指名文件的路径的话,系统默认是与src同一级别的目录路径!

  9. vue cli搭建的vue项目 不小心开了eslint 一直报黄色的警告

    报错必须处理,警告也忍不了,发现在bulid -webpack.base.config.js 里找到 const createLintingRule = () => ({ /*test: /\. ...

  10. VC&plus;&plus;:制作一个控件注册的小工具

    在平时的工作中,时常需要注册与反注册ActiveX控件,有时需要判断控件是否已经注册.   所以通过查找资料编写了一个控件注册的小工具,欢迎学习交流,不当之处请多多交流. 先直接上图:   主要代码: ...