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 =
dict =
s =
"leetcode"
,dict =
["leet", "code"]
.
Return true because
"leetcode"
can be segmented as "leet code"
.
Solution:
Dynamic programming
The recursion equation is straightforward, for res[i], if there exist an index j between 0 and i can make res[j]&&dict.contains(s.substring(j,i)) true, then res[i] will be true.
public boolean wordBreak(String s, Set<String> dict) {
if(s==null) return false;
if(s.length()==0) return true;
boolean[] res=new boolean[s.length()+1];
res[0]=true;
for(int i=0;i<s.length();i++){
for(int j=0;j<=i;j++){
if(res[j] && dict.contains(s.substring(j,i+1))){
res[i+1]=true;
break;
}
}
}
return res[s.length()];
}
No comments:
Post a Comment