首页 > 代码库 > Leetcode: Word Break
Leetcode: Word Break
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, givens = "leetcode",dict = ["leet", "code"].Return true because "leetcode" can be segmented as "leet code".
难度95，DP的经典题，参考了一下网上思路：
首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。
接下来我们套用上面的思路来解这道题。首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true，写成式子是
假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。代码如下：
1 public class Solution { 2 public boolean wordBreak(String s, Set<String> dict) { 3 if (s == null || s.length() == 0) { 4 return true; 5 } 6 if (s != null && s.length() != 0 && dict.isEmpty()) { 7 return false; 8 } 9 boolean[] res = new boolean[s.length()+1];10 res[0] = true;11 for (int i=0; i<s.length(); i++) {12 StringBuffer str = new StringBuffer(s.substring(0, i+1));13 for (int j=0; j<=i; j++) {14 if (res[j] && dict.contains(str.toString())) {15 res[i+1] = true;16 break;17 }18 str.deleteCharAt(0);19 }20 }21 22 return res[s.length()];23 }24 }
Leetcode: Word Break
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。