public boolean wordBreak(String s, Set<String> wordDict) {
if (s == null && wordDict == null)
return true;
if (s == null  wordDict == null)
return false;
//dp[i] represents if s.substring(0, i) is wordbreakable.
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
Java solution using DP


Great solution! Your code can be optimized a bit. In the inner loop, start from the tail to head instead of head to tail to check if the substring exists. We can break immediately when we see a match.
We can do even better if we precalculate the min and max of words' lengths in the dictionary. Just need to check from (iwordLengthMax) to (iwordLengthMin), and this will yield an algorithm of O(n) instead of O(n^2).
public class Solution { public boolean wordBreak(String s, Set<String> wordDict) { if (s == null && wordDict == null) return true; if (s == null  wordDict == null) return false; //dp[i] represents if s.substring(0, i+1) is wordbreakable. boolean[] dp = new boolean[s.length()+1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (int j = i1; j >=0; j) { if (dp[j] && wordDict.contains(s.substring(j, i))){ dp[i] = true; break; } } } return dp[s.length()]; } }

Thanks for your advices, it is smart! Thanks!
But I also have following thoughts.Basic Assumption: we assume on the characteristics of words in the dictionary.
(1)I think it is does not matter if j start from 0 or s.length  1. Let consider following cases,
s = "abcdef"
dict1 = {a, b, c, d, e, f}
dict2 = {a, bcdef}
For dict1, it is better to scan from tail. But for dict2, it is actually better to scan from front.
(2)O is the symbol for indicating worst case. Considering following case,
s = "abcdef"
dict2 = {a, bcdef}
If we scan from the tail, we still have O(n^2).
There may be misunderstanding in my thoughts. Please help me to clarify it and make progress.
Thanks!

I got your idea. But it could only optimize the algorithm for certain case, let us still consider a worst case.
s = "abcdefgh"
doct1 = {abcdefgq, a, b, c, d, e, f, g, h}
It actually still a O(n^2) solution. I think your idea could squeeze our search space, but we could not say it is O(n) method.
An way to optimize the code follows your idea is to try every "i  wordLength", where wordLength is the all possible word length in the dict.