Skip to content

Commit 3f39570

Browse files
MEDIUM/src/medium/WordBreak.java
1 parent 82067f3 commit 3f39570

File tree

1 file changed

+10
-3
lines changed

1 file changed

+10
-3
lines changed

MEDIUM/src/medium/WordBreak.java

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,21 +5,28 @@
55
public class WordBreak {
66

77
//Jiuzhang gives a very good illustration for this problem!
8+
89
public boolean wordBreak(String s, Set<String> wordDict) {
10+
int maxLen = Integer.MIN_VALUE;
11+
for(String word : wordDict){
12+
maxLen = (word.length() > maxLen) ? word.length() : maxLen;
13+
}
14+
915
int n = s.length();
1016
boolean[] dp = new boolean[n+1];
1117
dp[0] = true;
1218
for(int i = 1; i <= n; i++){
13-
for(int j = 0; j < i; j++){
14-
if(!dp[j]) continue;
19+
for(int j = 1; j <= i && j <= maxLen; j++){
20+
if(!dp[i-j]) continue;
1521

16-
String sub = s.substring(j, i);
22+
String sub = s.substring(i-j, i);
1723
if(wordDict.contains(sub)){
1824
dp[i] = true;
1925
break;
2026
}
2127
}
2228
}
29+
2330
return dp[n];
2431
}
2532

0 commit comments

Comments
 (0)