[LeetCode] 139. Word Break_ Medium tag: Dynamic Programming

时间:2022-10-23 00:17:56

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
  Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false 这个题目利用dynamic programming,因为是问yes/no,并且跟坐标有关。利用mem, mem[i] means whether the first i characters can be segment,
mem[i] = Or(mem[j] and s[j:i] is in WordDict). 需要注意的是/可以提高效率的是,跟[LeetCode] 132. Palindrome Partitioning II_ Hard tag: Dynamic Programming不同的是第二个
loop不需要每次都从0开始,因为如果我们知道dictionary中最大长度的word,只需要从i - maxlength来判断即可,然后当i 很小的时候有可能小于0, 所以用max(0,i - maxlength)来作为起始点。 T: O(n * maxl * maxl * len(wordDict)) # 前面n * maxl 因为两个loop,maxl * len(wordDict) 是判断一个string是否在wordDict里面的时间。
Code:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# Dynamic programming, T: O(len(s)*l*l*len(wordDict)) S: O(len(s))
maxl, n = 0, len(s)
for word in wordDict:
maxl = max(maxl, len(word))
mem = [False] * (n + 1)
mem[0] = True # mem[i] means whether the first i characters can be segment
for i in range(1, n + 1):
for j in range(max(0, i - maxl), i): #because the word been check should be at most with maxl length
if not mem[j]:
continue
if s[j:i] in wordDict:
mem[i] = True
break
return mem[n]

[LeetCode] 139. Word Break_ Medium tag: Dynamic Programming的更多相关文章

  1. [LeetCode] 55. Jump Game_ Medium tag: Dynamic Programming

    Given an array of non-negative integers, you are initially positioned at the first index of the arra ...

  2. [LeetCode] 62. Unique Paths_ Medium tag: Dynamic Programming

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The ...

  3. [LeetCode] 63. Unique Paths II_ Medium tag: Dynamic Programming

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The ...

  4. [LeetCode] 64. Minimum Path Sum_Medium tag: Dynamic Programming

    Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which ...

  5. [LeetCode] 152. Maximum Product Subarray_Medium tag: Dynamic Programming

    Given an integer array nums, find the contiguous subarray within an array (containing at least one n ...

  6. [LeetCode] 97. Interleaving String_ Hard tag: Dynamic Programming

    Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = ...

  7. [LeetCode] 115. Distinct Subsequences_ Hard tag: Dynamic Programming

    Given a string S and a string T, count the number of distinct subsequences of S which equals T. A su ...

  8. [LintCode] 77. Longest common subsequences_ Medium tag: Dynamic Programming

    Given two strings, find the longest common subsequence (LCS). Example Example 1: Input: "ABCD&q ...

  9. [LeetCode] 70. Climbing Stairs_ Easy tag: Dynamic Programming

    You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb ...

随机推荐

  1. Laravel中URL,ACTION,ROUTE区别

    创建路由如下所示: Route::get('articles',['uses'=>'ArticlesController@index','as'=>'articles.index']); ...

  2. [Everyday Mathematics]20150304

    证明: $$\bex \frac{2}{\pi}\int_0^\infty \frac{1-\cos 1\cos \lm-\lm \sin 1\sin \lm}{1-\lm^2}\cos \lm x\ ...

  3. HDU 5883 The Best Path

    The Best Path Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Tot ...

  4. C#让TopMost窗体弹出并置顶层但不获取当前输入焦点的终极办法

    为了使程序在弹出窗口时置顶层且不获取系统输入焦点,避免影响用户当前的操作,来电通来电弹屏软件尝试过N多种办法,例如:弹出前保存当前焦点窗口句柄,弹出时因为使用TopMost系统默认将焦点交给了弹出窗口 ...

  5. iOS 组件化

    iOS 组件化介绍 随着应用需求逐步迭代,应用的代码体积将会越来越大,为了更好的管理应用工程,我们开始借助CocoaPods版本管理工具对原有应用工程进行拆分.但是仅仅完成代码拆分还不足以解决业务之间 ...

  6. SEO -- WordPress怎设置百度站长链接自动提交

    百度站长平站更新了主动推送(实时)推送的方式,受到了广大站长的好评,但是对于使用WordPress的网站来说怎么设置自动提交呢,在这里介绍一种比较简单且有效的方法.我们可以使用 WP BaiDu Su ...

  7. Swift 3.0在集合类数据结构上的一些新变化

    一.Array数组的更改 array数组中修改的API示例如下: //创建大量相同元素的数组//创建有10个String类型元素的数组,并且每个元素都为字符串"Hello"//sw ...

  8. JVM笔记1-内存溢出分析问题与解决

    假设我们项目中JVM内存溢出了,大项目中上百万行代码,是很难定位的.因此我们需要借用一个Memory Analyzer工具, 官网地址为:http://www.eclipse.org/download ...

  9. js实现接口隔离

    昨天公司培训了接口隔离,简单说一下 接口隔离:类间的依赖关系应该建立在最小的接口上.接口隔离原则将非常庞大.臃肿的接口拆分成更小具体的接口,这样客户讲会只需要知道他们感兴趣的方法. 接口隔离原则的目的 ...

  10. MVC(面试)

    一般都是三层,表现层(UI).业务逻辑层(BLL).数据访问层(DAL),这些东西不用深究,别为了设计而设计就行.分三层是为了使项目架构体系更加清晰,而且项目参与人员的分工也可以更加明确,也有利于项目 ...