MEDIUM/src/medium/WordBreak.java

fishercoder1534 · fishercoder1534 · commit 4c6a31f96ce9 · 2016-09-14T00:01:31.000-07:00
diff --git a/MEDIUM/src/medium/WordBreak.java b/MEDIUM/src/medium/WordBreak.java
@@ -6,7 +6,7 @@ public class WordBreak {
 
     //Jiuzhang gives a very good illustration for this problem!
 
-    public boolean wordBreak(String s, Set<String> wordDict) {
+    public boolean wordBreak_2ms(String s, Set<String> wordDict) {
         int maxLen = Integer.MIN_VALUE;
         for(String word : wordDict){
             maxLen = (word.length() > maxLen) ? word.length() : maxLen;
@@ -16,10 +16,10 @@ public boolean wordBreak(String s, Set<String> wordDict) {
         boolean[] dp = new boolean[n+1];
         dp[0] = true;
         for(int i = 1; i <= n; i++){
-            for(int j = 1; j <= i && j <= maxLen; j++){
-                if(!dp[i-j]) continue;
+            for(int lastWordLength = 1; lastWordLength <= i && lastWordLength <= maxLen; lastWordLength++){
+                if(!dp[i-lastWordLength]) continue;
                 
-                String sub = s.substring(i-j, i);
+                String sub = s.substring(i-lastWordLength, i);
                 if(wordDict.contains(sub)){
                     dp[i] = true;
                     break;
@@ -29,5 +29,29 @@ public boolean wordBreak(String s, Set<String> wordDict) {
         
         return dp[n];
     }
+    
+
+    //this is much slower, although AC'ed on Leetcode, TLE on Lintcode.
+    //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
+    //right-most true element, then check that substring. That's why we could write wordBreak_2ms() above.
+    public boolean wordBreak_14ms(String s, Set<String> wordDict) {
+        int n = s.length();
+        boolean[] dp = new boolean[n+1];
+        dp[0] = true;
+        for(int i = 1; i <= n; i++){
+            for(int j = 0; j < i; j++){
+                if(!dp[j]) continue;
+                
+                String sub = s.substring(j, i);
+                if(wordDict.contains(sub)){
+                    dp[i] = true;
+                    break;
+                }
+            }
+        }
+        
+        return dp[n];
+    }
+
 
 }
