refactor 140

fishercoder1534 · fishercoder1534 · commit da49f23d96d9 · 2018-04-29T07:34:36.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_140.java b/src/main/java/com/fishercoder/solutions/_140.java
@@ -6,44 +6,76 @@
 
 /**
  * 140. Word Break II
- *
- * Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
 
+ Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,
+ add spaces in s to construct a sentence where each word is a valid dictionary word.
  Return all such possible sentences.
 
- For example, given
- s = "catsanddog",
- dict = ["cat", "cats", "and", "sand", "dog"].
+ Note:
 
- A solution is ["cats and dog", "cat sand dog"].
+ The same word in the dictionary may be reused multiple times in the segmentation.
+ You may assume the dictionary does not contain duplicate words.
 
+ Example 1:
+
+ Input:
+ s = "catsanddog"
+ wordDict = ["cat", "cats", "and", "sand", "dog"]
+ Output:
+ [
+ "cats and dog",
+ "cat sand dog"
+ ]
+
+ Example 2:
+
+ Input:
+ s = "pineapplepenapple"
+ wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
+ Output:
+ [
+ "pine apple pen apple",
+ "pineapple pen apple",
+ "pine applepen apple"
+ ]
+ Explanation: Note that you are allowed to reuse a dictionary word.
+
+ Example 3:
+
+ Input:
+ s = "catsandog"
+ wordDict = ["cats", "dog", "sand", "and", "cat"]
+ Output:
+ []
  */
+
 public class _140 {
+  public static class Solution1 {
     public List<String> wordBreak(String s, List<String> wordDict) {
-        return dfs(s, wordDict, new HashMap<>());
+      return dfs(s, wordDict, new HashMap<>());
     }
 
     List<String> dfs(String s, List<String> wordDict, HashMap<String, List<String>> map) {
-        if (map.containsKey(s)) {
-            return map.get(s);
-        }
+      if (map.containsKey(s)) {
+        return map.get(s);
+      }
 
-        ArrayList<String> result = new ArrayList<>();
-        if (s.length() == 0) {
-            result.add("");
-            return result;
-        }
+      ArrayList<String> result = new ArrayList<>();
+      if (s.length() == 0) {
+        result.add("");
+        return result;
+      }
 
-        for (String word : wordDict) {
-            if (s.startsWith(word)) {
-                List<String> subList = dfs(s.substring(word.length()), wordDict, map);
-                for (String sub : subList) {
-                    result.add(word + (sub.length() == 0 ? "" : " ") + sub);
-                }
-            }
+      for (String word : wordDict) {
+        if (s.startsWith(word)) {
+          List<String> subList = dfs(s.substring(word.length()), wordDict, map);
+          for (String sub : subList) {
+            result.add(word + (sub.length() == 0 ? "" : " ") + sub);
+          }
         }
-        map.put(s, result);
-        return result;
+      }
+      map.put(s, result);
+      return result;
     }
-
-}
+  }
+}
