refactor 139

fishercoder1534 · fishercoder1534 · commit f16f03995284 · 2020-06-25T10:25:57.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_139.java b/src/main/java/com/fishercoder/solutions/_139.java
@@ -1,10 +1,30 @@
 package com.fishercoder.solutions;
 
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 
 public class _139 {
 
     public static class Solution1 {
+        public boolean wordBreak(String s, List<String> wordDict) {
+            return wordBreak(s, new HashSet(wordDict), 0);
+        }
+
+        public boolean wordBreak(String s, Set<String> wordDict, int start) {
+            if (start == s.length()) {
+                return true;
+            }
+            for (int end = start + 1; end <= s.length(); end++) {
+                if (wordDict.contains(s.substring(start, end)) && wordBreak(s, wordDict, end)) {
+                    return true;
+                }
+            }
+            return false;
+        }
+    }
+
+    public static class Solution2 {
         /**
          * this beats 70.46% submission.
          */
@@ -24,7 +44,7 @@ public boolean wordBreak(String s, List<String> wordDict) {
         }
     }
 
-    public static class Solution2 {
+    public static class Solution3 {
         /**
          * Added pruning.
          * this beats 89.91% submissions.
@@ -53,7 +73,7 @@ public boolean wordBreak(String s, List<String> wordDict) {
         }
     }
 
-    public static class Solution3 {
+    public static class Solution4 {
         /**
          * Added pruning, plus start from the end to check.
          * This beats 95.20% submissions.
diff --git a/src/test/java/com/fishercoder/_139Test.java b/src/test/java/com/fishercoder/_139Test.java
@@ -11,25 +11,75 @@
 import static junit.framework.Assert.assertEquals;
 
 public class _139Test {
-  private static _139.Solution1 solution1;
-  private static _139.Solution2 solution2;
-  private static _139.Solution3 solution3;
-  private static String s;
-  private static List<String> wordDict;
-
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _139.Solution1();
-    solution2 = new _139.Solution2();
-    solution3 = new _139.Solution3();
-  }
-
-  @Test
-  public void test1() {
-    s = "leetcode";
-    wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
-    assertEquals(true, solution1.wordBreak(s, wordDict));
-    assertEquals(true, solution2.wordBreak(s, wordDict));
-    assertEquals(true, solution3.wordBreak(s, wordDict));
-  }
+    private static _139.Solution1 solution1;
+    private static _139.Solution2 solution2;
+    private static _139.Solution3 solution3;
+    private static _139.Solution4 solution4;
+    private static String s;
+    private static List<String> wordDict;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _139.Solution1();
+        solution2 = new _139.Solution2();
+        solution3 = new _139.Solution3();
+        solution4 = new _139.Solution4();
+    }
+
+    @Test
+    public void test1() {
+        s = "leetcode";
+        wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
+        assertEquals(true, solution1.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test2() {
+        s = "leetcode";
+        wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
+        assertEquals(true, solution2.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test3() {
+        s = "leetcode";
+        wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
+        assertEquals(true, solution3.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test4() {
+        s = "leetcode";
+        wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
+        assertEquals(true, solution4.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test5() {
+        s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
+        wordDict = new ArrayList<>(Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"));
+        assertEquals(true, solution1.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test6() {
+        s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
+        wordDict = new ArrayList<>(Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"));
+        assertEquals(true, solution2.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test7() {
+        s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
+        wordDict = new ArrayList<>(Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"));
+        assertEquals(true, solution3.wordBreak(s, wordDict));
+    }
+
+    @Test
+    public void test8() {
+        s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
+        wordDict = new ArrayList<>(Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"));
+        assertEquals(true, solution4.wordBreak(s, wordDict));
+    }
+
 }
