package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/word-break-ii/
 */
public class Problem140 {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>();
        for (String word : wordDict) {
            words.add(word);
        }
        List<String> result = new ArrayList<>();
        wordBreak(s, words, 0, 1, new ArrayList<>(), result);
        return result;
    }

    private static void wordBreak(String s, Set<String> words, int i, int j, List<String> tmp,
                                  List<String> result) {
        if (j > s.length()) {
            if (i == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < tmp.size(); k++) {
                    if (k == 0) {
                        sb.append(tmp.get(k));
                    } else {
                        sb.append(" " + tmp.get(k));
                    }
                }
                result.add(sb.toString());
            }
            return;
        }
        String sub = s.substring(i, j);
        if (words.contains(sub)) {
            tmp.add(sub);
            wordBreak(s, words, j, j + 1, tmp, result);
            tmp.remove(tmp.size() - 1);
        }
        wordBreak(s, words, i, j + 1, tmp, result);
    }

    public static void main(String[] args) {
        Problem140 prob = new Problem140();
        System.out.println(prob.wordBreak("catsanddog",
            Arrays.asList("cat", "cats", "and", "sand", "dog"))); // ["cats and dog", "cat sand dog"]
        System.out.println(prob.wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
            Arrays.asList("a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa")));
    }
}

@@ -57,22 +57,23 @@
 va.util.
-Arrays
+HashMap
 ;%0Aimport
@@ -111,24 +111,46 @@
 .util.List;%0A
+import java.util.Map;%0A
 import java.
@@ -446,132 +446,51 @@
     
-List%3CString%3E result = new ArrayList%3C%3E();%0A        wordBreak(s, words, 0, 1, new ArrayList%3C%3E(), result);%0A        return result
+return wordBreak(s, words, new HashMap%3C%3E())
 ;%0A  
@@ -513,20 +513,28 @@
  static 
-void
+List%3CString%3E
  wordBre
@@ -569,20 +569,18 @@
 ds, 
-int i, int j
+Map%3CString
 , Li
@@ -593,105 +593,67 @@
 ing%3E
- tmp,%0A                                  List%3CString%3E result) %7B%0A        if (j %3E s.length()) %7B%0A    
+%3E memo) %7B%0A        List%3CString%3E result = new ArrayList%3C%3E();%0A
     
@@ -664,21 +664,30 @@
 if (
-i
+s
  == 
-s.length
+null %7C%7C s.isEmpty
 ()) 
@@ -704,50 +704,21 @@
     
-    StringBuilder sb = new StringBuilder()
+return result
 ;%0A  
@@ -723,24 +723,26 @@
         
+%7D%0A
         
 for (int
@@ -737,125 +737,64 @@
     
-for (int k = 0; k %3C tmp.size(); k++) %7B%0A                    if (k == 0) %7B%0A                        sb.append(tmp
+if (memo.containsKey(s)) %7B%0A            return memo
 .get(
-k)
+s
 );%0A 
@@ -804,209 +804,131 @@
     
-       
-     %7D else %7B%0A                        sb.append(%22 %22 + tmp.get(k));%0A                    %7D%0A                %7D%0A                result.add(sb.toString());%0A            %7D%0A            return;%0A    
+%7D%0A        if (words.contains(s)) %7B%0A            result.add(s);%0A        %7D%0A        for (int i = 1; i %3C s.length(); i++) %7B%0A
     
-%7D%0A
     
@@ -957,19 +957,16 @@
 string(i
-, j
 );%0A     
@@ -960,32 +960,36 @@
 ing(i);%0A        
+  
+  
 if (words.contai
@@ -1015,117 +1015,136 @@
     
-tmp.add(sub);%0A            wordBreak(s, words, j, j + 1, tmp, result);%0A            tmp.remove(tmp.size() - 1);
+    List%3CString%3E strings = wordBreak(s.substring(0, i), words, memo);%0A                for (int j = 0; j %3C strings.size(); j++) %7B
 %0A   
@@ -1148,26 +1148,24 @@
         
-%7D%0A
         
 wordBrea
@@ -1160,625 +1160,144 @@
     
-wordBreak(s, words, i, j + 1, tmp, result);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem140 prob = new Problem140();%0A        System.out.println(prob.wordBreak(%22catsanddog%22,%0A            Arrays.asList(%22cat%22, %22cats%22, %22and%22, %22sand%22, %22dog%22))); // %5B%22cats and dog%22, %22cat sand dog%22%5D%0A        System.out.println(prob.wordBreak(%22aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%22,%0A            Arrays.asList(%22a%22, %22aa%22, %22aaa%22, %22aaaa%22, %22aaaaa%22, %22aaaaaa%22, %22aaaaaaa%22, %22aaaaaaaa%22, %22aaaaaaaaa%22, %22aaaaaaaaaa%22)))
+    result.add(strings.get(j) + %22 %22 + sub);%0A                %7D%0A            %7D%0A        %7D%0A        memo.put(s, result);%0A        return result
 ;%0A  

Solve problem 140