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) {
        // TODO
        Set<String> words = new HashSet<>();
        for (String word : wordDict) {
            words.add(word);
        }
        List<String> result = new ArrayList<>();
        wordBreak(s, words, 0, 1, "", result);
        return result;
    }

    private static void wordBreak(String s, Set<String> words, int i, int j, String accu,
                                  List<String> result) {
        if (j > s.length()) {
            if (i == s.length()) {
                result.add(accu);
            }
            return;
        }
        String sub = s.substring(i, j);
        if (words.contains(sub)) {
            String newAccu = accu;
            if (newAccu.isEmpty()) {
                newAccu = sub;
            } else {
                newAccu += " " + sub;
            }
            wordBreak(s, words, j, j + 1, newAccu, result);
        }
        wordBreak(s, words, i, j + 1, accu, 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"]
    }
}

@@ -292,24 +292,8 @@
 ) %7B%0A
-        // TODO%0A
     
@@ -498,10 +498,25 @@
  1, 
-%22%22
+new ArrayList%3C%3E()
 , re
@@ -633,19 +633,24 @@
  j, 
+List%3C
 String
- accu
+%3E tmp
 ,%0A  
@@ -789,23 +789,45 @@
     
-result.add(accu
+StringBuilder sb = new StringBuilder(
 );%0A 
@@ -841,29 +841,50 @@
     
-%7D%0A
     
-        return;
+for (int k = 0; k %3C tmp.size(); k++) %7B
 %0A   
@@ -888,26 +888,24 @@
         
-%7D%0A
         
 String s
@@ -900,198 +900,271 @@
     
-String sub = s.substring(i, j);%0A        if (words.contains(sub)) %7B%0A            String newAccu = accu;%0A            if (newAccu.isEmpty()) %7B%0A                newAccu = sub;%0A            %7D else %7B
+    if (k == 0) %7B%0A                        sb.append(tmp.get(k));%0A                    %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   
@@ -1168,24 +1168,26 @@
         
+%7D%0A
         
 newAccu 
@@ -1182,43 +1182,100 @@
     
-newAccu += %22 %22 + sub;%0A            %7D
+String sub = s.substring(i, j);%0A        if (words.contains(sub)) %7B%0A            tmp.add(sub);
 %0A   
@@ -1317,15 +1317,11 @@
  1, 
-newAccu
+tmp
 , re
@@ -1319,32 +1319,72 @@
 , tmp, result);%0A
+            tmp.remove(tmp.size() - 1);%0A
         %7D%0A      
@@ -1419,12 +1419,11 @@
  1, 
-accu
+tmp
 , re
@@ -1683,16 +1683,337 @@
 d 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)));%0A
     %7D%0A%7D%0A

Update problem 140