Dynamic programing question… need to think that way… it is a technique/skill
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
if(s == null || dict == null){
return false;
}
int length = s.length();
boolean[] process = new boolean[length+1]; //use bits if space is critical.
process[length] = true;
for(int i = length - 1; i >= 0; i--){
for(int j = i + 1; j < length + 1; j++){
if(dict.contains(s.substring(i, j)) && process[j] == true){
process[i] = true;
break;
}
}
}
return process[0];
}
}
没有评论:
发表评论