word break II

fishercoder1534 · fishercoder1534 · commit c0bc3df07255 · 2016-10-04T19:34:20.000-07:00
diff --git a/HARD/src/hard/WordBreakII.java b/HARD/src/hard/WordBreakII.java
@@ -0,0 +1,57 @@
+package hard;
+import java.util.*;
+/**
+ * Created by fishercoder1534 on 10/4/16.
+ */
+public class WordBreakII {
+    public List<String> wordBreak(String s, Set<String> wordDict) {
+        return dfs(s, wordDict, new HashMap<String, ArrayList<String>>());
+    }
+
+    private List<String> dfs(String s, Set<String> wordDict,
+                             HashMap<String, ArrayList<String>> map) {
+        if(map.containsKey(s)){
+            return map.get(s);
+        }
+
+        ArrayList<String> res = new ArrayList<String>();
+        if(s.length() == 0){
+            res.add("");
+            return res;
+        }
+
+        for(String word : wordDict){
+            if(s.startsWith(word)){
+                List<String> subList = dfs(s.substring(word.length()), wordDict, map);
+                for(String sub : subList){
+                    res.add(word + (sub.length() == 0 ? "" : " ") + sub);
+                }
+            }
+        }
+        map.put(s, res);
+        return res;
+    }
+
+    public static void main(String...strings){
+        List<String> temp = new ArrayList<String>();
+        System.out.println(temp);
+        List<String> temp2 = new ArrayList<String>(temp);
+        temp2.add("");
+        System.out.println(temp2);
+
+        WordBreakII test = new WordBreakII();
+        Set<String> wordDict = new HashSet<>();
+        wordDict.add("cat");
+        wordDict.add("cats");
+        wordDict.add("sand");
+        wordDict.add("and");
+        wordDict.add("dog");
+        String s = "catsanddog";
+//        List<String> list = test.wordBreak(s, wordDict);
+        List<String> list = test.wordBreak(s, wordDict);
+        for(String word : list){
+            System.out.print(word + ", ");
+        }
+        System.out.println();
+    }
+}
diff --git a/README.md b/README.md
@@ -2,6 +2,7 @@
 |  #  |      Title     |      Solutions   | Time  | Space  | Difficulty | Tag | Notes
 |-----|----------------|------------------|-------|--------|------------|-----|------
 |278|[First Bad Version](https://leetcode.com/problems/first-bad-version/)|[Solution](../../blob/master/EASY/src/easy/FirstBadVersion.java)| O(logn)|O(1) | Easy| Binary Search
+|140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../blob/master/HARD/src/hard/WordBreakII.java)| |O(n^2) | Hard| Backtracking/DFS
 |139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../blob/master/MEDIUM/src/medium/WordBreak.java)| O(n^2)|O(n) | Medium| DP
 |133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../blob/master/MEDIUM/src/medium/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS 
 |91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../blob/master/MEDIUM/src/medium/DecodeWays.java)| O(n)|O(n) | Medium| DP
