首页 > 代码库 > [leetcode]Word Break
[leetcode]Word Break
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, given
s ="leetcode",
dict =["leet", "code"].Return true because
"leetcode"can be segmented as"leet code".
算法思路：
思路1.dfs。肯定会超时，但是这里捡了leetcode的漏，本题case比较强的都是在结尾出现了坑，这道题偷懒，从后往前找单词。再递归。居然过了。。。。
1 public class Solution { 2 public boolean wordBreak(String s, Set<String> dict) { 3 if(s.length() == 0) return true; 4 for(String word : dict){ 5 if(s.endsWith(word)){ 6 if(!wordBreak(s.substring(0, s.length() - word.length()),dict)) continue; 7 else return true; 8 } 9 }10 return false;11 }12 }
思路2：既然递归超时，那就用DP吧，dp[i]表示前i长度字符串能否成功分解。
代码如下：
1 public class Solution { 2 public boolean wordBreak(String s, Set<String> dict) { 3 int length = s.length(); 4 if(length == 0) return true; 5 boolean[] dp = new boolean[length + 1]; 6 dp[0] = true; 7 for(int i = 0; i <= length; i++){ 8 if(!dp[i]) continue; 9 for(String word:dict){10 if(s.substring(i).startsWith(word)){11 dp[i + word.length()] = true;12 }13 }14 }15 return dp[length];16 }17 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。