问题描述:
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode"
,
dict = ["leet", "code"]
.
Return true because "leetcode"
can be segmented as "leet code"
.
原问题链接:https://leetcode.com/problems/word-break/
问题分析
从问题的要求来看,需要判断是否可以将给定的字符串拆分成若干个子串,使得里面每个子串都可以在给定的字典集中找到。从一种最通用的情况来看,假定一个数组的长度为n。对于里面索引位置为i的点,假设存在有i到n的这一段在集合中可以找到,那么我们这个问题是否有解就取决于前面0到i - 1的这一段的情况了。相当于我们这个问题递归的缩小到更小的串里面了。
而从问题最小的形式来看,对于长度为0的串,我们可以认为它是可以在字典集合中找到的。这样,我们就构成了一个简单的递推关系:
f(n) = for(i = 0; i < n; i++) { if(s.substring(i, n) in set) then f(i) is a possible solution }
既然是这么一个递归的关系,我们如果直接用递归的话,会发现有一些子串的递归情况可能会反复用到。这样可以考虑用动态规划的方法。
在详细的实现里,我们定义一个boolean[n + 1]canBrerak的串。canBreak[0] = true。表示0个字符的情况。对于后续的元素,我们根据前面的条件来判断设置canBreak[i]的值。只要找到一个满足canBreak[i]为true的值,我们就可以继续考虑canBreak[i+1]的情况了。
详细的代码实现如下:
public class Solution { public boolean wordBreak(String s, Set<String> dict) { if(s == null || s.length() == 0) return true; boolean[] canBreak = new boolean[s.length() + 1]; canBreak[0] = true; for(int i = 1; i <= s.length(); i++) { for(int j = 0; j < i; j++) { if(canBreak[j] && dict.contains(s.substring(j, i))) { canBreak[i] = true; break; } } } return canBreak[s.length()]; } }
相关推荐
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Example Example 1...
leetcode 苹果断字 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。 笔记: 字典中的同一个词可能会在切分中重复使用多次。...word. E
断字leetcode WordBreak-Leetcode-139 Leetcode 问题 139(中) 问题中使用的技术:动态规划
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
Break](Leetcode 问题/数组和字符串/139.word_break.md) [140. Word Break ii](Leetcode 问题/数组和字符串/140.word_break_ii.md) [151. 反转字符串中的单词](Leetcode Problems/Array and String/151.reverse_...
lru缓存leetcode Go 中解决的一些 Leetcode 问题 大批 3sum-0015 买卖股票的最佳时机-0121 最多水的容器-0011 contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 ...word-break-0139 图形
断字leetcode 断字 “断字”问题的解决方案。 用 C# 编写 Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. ...
动态编程递归无重复每个子问题只能评估一次天真的递归方法由于重复而花费指数时间自上而下的回忆这是递归的深度优先搜索实现缓存重复工作自下而上基于依赖图将递归转换为依赖图它是有向无环图您可以使用拓扑排序对......
Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of ...