public boolean wordBreak(String s, Set<String> wordDict) {
int maxWord = getMax(wordDict);
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i ++) {
int start = Math.max(1, i  maxWord);
for (int j = start; j <= i; j++) {
if (dp[j  1] && wordDict.contains(s.substring(j  1, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
private int getMax(Set<String> wordDict) {
int max = 0;
for (String str : wordDict) {
max = Math.max(max, str.length());
}
return max;
}
My Java DP solution beats 93.83%


@biedengle2
Ah, you are trying to apply some heuristic to always pick try the longest word in the diction as the potential candidate.However, for the time complexity wise, I think the time complexity still O(stringlen^2), is that true?

@kun5 Not really, if the strings in wordDict is short (<r) then the running time is r*s.length()

@kun5 unfortunately the time complexity is O(n^3) where n is the word length. because substring takes O(n)