[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 }