@@ -6,7 +6,7 @@ public class WordBreak {
66
77//Jiuzhang gives a very good illustration for this problem!
88
9- public boolean wordBreak (String s ,Set <String >wordDict ) {
9+ public boolean wordBreak_2ms (String s ,Set <String >wordDict ) {
1010int maxLen =Integer .MIN_VALUE ;
1111for (String word :wordDict ){
1212maxLen = (word .length () >maxLen ) ?word .length () :maxLen ;
@@ -16,10 +16,10 @@ public boolean wordBreak(String s, Set<String> wordDict) {
1616boolean []dp =new boolean [n +1 ];
1717dp [0 ] =true ;
1818for (int i =1 ;i <=n ;i ++){
19- for (int j =1 ;j <=i &&j <=maxLen ;j ++){
20- if (!dp [i -j ])continue ;
19+ for (int lastWordLength =1 ;lastWordLength <=i &&lastWordLength <=maxLen ;lastWordLength ++){
20+ if (!dp [i -lastWordLength ])continue ;
2121
22- String sub =s .substring (i -j ,i );
22+ String sub =s .substring (i -lastWordLength ,i );
2323if (wordDict .contains (sub )){
2424dp [i ] =true ;
2525break ;
@@ -29,5 +29,29 @@ public boolean wordBreak(String s, Set<String> wordDict) {
2929
3030return dp [n ];
3131 }
32+
33+
34+ //this is much slower, although AC'ed on Leetcode, TLE on Lintcode.
35+ //This is because in the inner for loop, this method is looping from left to right which is unnecessary, we only need to find the
36+ //right-most true element, then check that substring. That's why we could write wordBreak_2ms() above.
37+ public boolean wordBreak_14ms (String s ,Set <String >wordDict ) {
38+ int n =s .length ();
39+ boolean []dp =new boolean [n +1 ];
40+ dp [0 ] =true ;
41+ for (int i =1 ;i <=n ;i ++){
42+ for (int j =0 ;j <i ;j ++){
43+ if (!dp [j ])continue ;
44+
45+ String sub =s .substring (j ,i );
46+ if (wordDict .contains (sub )){
47+ dp [i ] =true ;
48+ break ;
49+ }
50+ }
51+ }
52+
53+ return dp [n ];
54+ }
55+
3256
3357}