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. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
一刷
题解：
最简单的方法：dfs
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
return dfs(s, set, 0);
}
public boolean dfs(String s, Set<String> set, int pos){
if(pos == s.length()) return true;
for(int i=pos+1; i<=s.length(); i++){
if(set.contains(s.substring(pos, i))){
//System.out.println(s.substring(pos, i));
if(dfs(s, set, i)) return true;
}
}
return false;
}
}
但是在
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
会超时， O(n!)。考虑用dp来做：
O(n^2)
- 可以直接由list转为set, 在构造set时传入list为构造函数参数
- dynamic programming,
dp[i] = dp[j] && set.contains(s.subString(i, j)) - 要注意设置dp[0]=true, 对于DP来说，设置初始值都是十分重要的。
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<String>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;//very important!!!
for(int i=1; i<=s.length(); i++){
for(int j = 0; j<i; j++){
if(dp[j] && dict.contains(s.substring(j, i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
二刷
DP
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int right = 1; right<=s.length(); right++){
for(int left = right-1; left>=0; left--){
if(dp[left] && dict.contains(s.substring(left, right))) {
dp[right] = true;//not include right
break;
}
}
}
return dp[s.length()];
}
}
