# My Java DP solution beats 93.83%

• ``````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;
}``````

• @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)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.