public boolean wordBreak(String s, Set<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
int maxLen = 0;
for (String str : wordDict) {
maxLen = Math.max(maxLen, str.length());
}
for(int end = 1;end<s.length()+1;end++){
if(wordDict.contains(s.substring(0,end))) {
dp[end] = true;
continue;
}
//Here the starting value of i is optimized from 1 to endmaxLen>1?endmaxLen:1
//since the difference between i and end cannot be bigger than the maximum length of string in the dictionary.
// If it is set to 1, it will waste a lot of time on computing meaningless i values.
for(int i = endmaxLen>1?endmaxLen:1;i<end;i++){
if(dp[i]==true&&wordDict.contains(s.substring(i,end))){
dp[end] = true;
break;
}
}
}
if(dp[s.length()]) return true;
else return false;
}
Java 2ms optimized DP solution.


Shorten @Nakanu code :)
The thinking is similar to BFS, in which way it looks forwardmaxLen
steps. However, the major difference here is that it looks backwardmaxLen
steps at most and can terminate in advance.public boolean wordBreak(String s, Set<String> wordDict) { boolean[] dp = new boolean[s.length()+1]; dp[0] = true; int maxLen = 0; for (String str : wordDict) maxLen = Math.max(maxLen, str.length()); for(int end = 1; end < s.length()+1; end++) { // looks back for(int j = endmaxLen > 0? endmaxLen : 0;j < end; if(dp[i] && wordDict.contains(s.substring(i,end))){ dp[end] = true; break; } } } return dp[s.length()]; }