package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 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.

 Return all such possible sentences.

 For example, given
 s = "catsanddog",
 dict = ["cat", "cats", "and", "sand", "dog"].

 A solution is ["cats and dog", "cat sand dog"].

 */
public class _140 {
    public List<String> wordBreak(String s, List<String> wordDict) {
        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);
        }

        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);
                }
            }
        }
        map.put(s, result);
        return result;
    }

}
@@ -137,13 +137,9 @@
  II%0A
- *%0A *
+%0A
  Giv
@@ -143,16 +143,26 @@
 Given a 
+non-empty 
 string s
@@ -183,22 +183,55 @@
 ary 
-of words dict,
+wordDict containing a list of non-empty words,%0A
  add
@@ -311,17 +311,16 @@
 y word.%0A
-%0A
  Return 
@@ -354,26 +354,184 @@
 .%0A%0A 
-For example, given
+Note:%0A%0A The same word in the dictionary may be reused multiple times in the segmentation.%0A You may assume the dictionary does not contain duplicate words.%0A%0A Example 1:%0A%0A Input:
 %0A s 
@@ -548,12 +548,15 @@
 dog%22
-,
 %0A 
-d
+wordD
 ict 
@@ -598,65 +598,428 @@
 og%22%5D
-.%0A%0A A solution is %5B%22cats and dog%22, %22cat sand dog%22%5D.%0A
+%0A Output:%0A %5B%0A %22cats and dog%22,%0A %22cat sand dog%22%0A %5D%0A%0A Example 2:%0A%0A Input:%0A s = %22pineapplepenapple%22%0A wordDict = %5B%22apple%22, %22pen%22, %22applepen%22, %22pine%22, %22pineapple%22%5D%0A Output:%0A %5B%0A %22pine apple pen apple%22,%0A %22pineapple pen apple%22,%0A %22pine applepen apple%22%0A %5D%0A Explanation: Note that you are allowed to reuse a dictionary word.%0A%0A Example 3:%0A%0A Input:%0A s = %22catsandog%22%0A wordDict = %5B%22cats%22, %22dog%22, %22sand%22, %22and%22, %22cat%22%5D%0A Output:%0A %5B%5D
 %0A */%0A
+%0A
 publ
@@ -1034,16 +1034,50 @@
  _140 %7B%0A
+  public static class Solution1 %7B%0A
     publ
@@ -1139,26 +1139,24 @@
 ct) %7B%0A      
-  
 return dfs(s
@@ -1285,26 +1285,24 @@
 ap) %7B%0A      
-  
 if (map.cont
@@ -1319,28 +1319,24 @@
 ) %7B%0A        
-   
- 
 return map.g
@@ -1340,34 +1340,32 @@
 p.get(s);%0A      
-  
 %7D%0A%0A        Array
@@ -1357,18 +1357,16 @@
 %0A%0A      
- 
- 
 ArrayLis
@@ -1405,26 +1405,24 @@
 %3C%3E();%0A      
-  
 if (s.length
@@ -1432,36 +1432,32 @@
 == 0) %7B%0A        
- 
-   
 result.add(%22%22);%0A
@@ -1460,28 +1460,24 @@
 %22);%0A        
- 
-   
 return resul
@@ -1481,31 +1481,27 @@
 sult;%0A      
-  
 %7D%0A%0A
-  
       for (S
@@ -1533,20 +1533,16 @@
         
-  
-  
 if (s.st
@@ -1555,30 +1555,24 @@
 th(word)) %7B%0A
-      
           Li
@@ -1650,22 +1650,16 @@
         
-      
 for (Str
@@ -1679,24 +1679,16 @@
 List) %7B%0A
-        
         
@@ -1762,26 +1762,18 @@
     
-   
-   %7D%0A  
+%7D%0A
         
   %7D%0A
@@ -1764,30 +1764,26 @@
   %7D%0A        
-  %7D%0A  
+%7D%0A
       %7D%0A    
@@ -1784,18 +1784,16 @@
 %7D%0A      
-  
 map.put(
@@ -1804,18 +1804,16 @@
 esult);%0A
-  
       re
@@ -1835,6 +1835,10 @@
   %7D%0A
+  %7D
 %0A%7D
+%0A

refactor 140