package com.fishercoder.solutions;

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

/**
 * 140. Word Break II

 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.

 Note:

 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<>());
    }

    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;
    }
  }
}

@@ -111,915 +111,8 @@
 t;%0A%0A
-/**%0A * 140. Word Break II%0A%0A Given a non-empty string s and a dictionary wordDict containing a list of non-empty words,%0A add spaces in s to construct a sentence where each word is a valid dictionary word.%0A Return all such possible sentences.%0A%0A 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 = %22catsanddog%22%0A wordDict = %5B%22cat%22, %22cats%22, %22and%22, %22sand%22, %22dog%22%5D%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
@@ -127,16 +127,18 @@
  _140 %7B%0A
+  
   public
@@ -163,24 +163,28 @@
 tion1 %7B%0A    
+   
+ 
 public List%3C
@@ -232,24 +232,30 @@
 wordDict) %7B%0A
+      
       return
@@ -290,27 +290,35 @@
 p%3C%3E());%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A    
     List%3CStr
@@ -392,24 +392,30 @@
 ng%3E%3E map) %7B%0A
+      
       if (ma
@@ -438,24 +438,32 @@
 ) %7B%0A        
+   
+     
 return map.g
@@ -471,27 +471,39 @@
 t(s);%0A      
-%7D%0A%0A
+      %7D%0A%0A      
       ArrayL
@@ -542,16 +542,22 @@
 st%3C%3E();%0A
+      
       if
@@ -577,32 +577,40 @@
 == 0) %7B%0A        
+   
+     
 result.add(%22%22);%0A
@@ -613,24 +613,32 @@
 %22);%0A        
+   
+     
 return resul
@@ -642,27 +642,39 @@
 sult;%0A      
-%7D%0A%0A
+      %7D%0A%0A      
       for (S
@@ -690,32 +690,40 @@
 d : wordDict) %7B%0A
+        
         if (s.st
@@ -742,32 +742,42 @@
 d)) %7B%0A          
+        
+  
 List%3CString%3E sub
@@ -831,16 +831,26 @@
 , map);%0A
+          
         
@@ -884,32 +884,44 @@
 ) %7B%0A            
+     
+       
 result.add(word 
@@ -967,26 +967,44 @@
 ;%0A          
+         
+ 
 %7D%0A
+        
         %7D%0A  
@@ -1007,24 +1007,36 @@
 %7D%0A      
-%7D%0A
+      %7D%0A  
       
+    
 map.put(
@@ -1049,24 +1049,30 @@
 ult);%0A      
+    
+  
 return resul
@@ -1078,16 +1078,22 @@
 lt;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 140