File tree Expand file tree Collapse file tree 1 file changed +10
-3
lines changed Expand file tree Collapse file tree 1 file changed +10
-3
lines changed Original file line number Diff line number Diff line change 5
5
public class WordBreak {
6
6
7
7
//Jiuzhang gives a very good illustration for this problem!
8
+
8
9
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
+
9
15
int n = s .length ();
10
16
boolean [] dp = new boolean [n +1 ];
11
17
dp [0 ] = true ;
12
18
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 ;
15
21
16
- String sub = s .substring (j , i );
22
+ String sub = s .substring (i - j , i );
17
23
if (wordDict .contains (sub )){
18
24
dp [i ] = true ;
19
25
break ;
20
26
}
21
27
}
22
28
}
29
+
23
30
return dp [n ];
24
31
}
25
32
You can’t perform that action at this time.
0 commit comments