package leetcode;

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);
        }
        return null;
    }

    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"]
    }
}

@@ -12,16 +12,44 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0A
 import j
@@ -65,16 +65,16 @@
 Arrays;%0A
-
 import j
@@ -439,19 +439,788 @@
     
-return null
+List%3CString%3E result = new ArrayList%3C%3E();%0A        wordBreak(s, words, 0, 1, %22%22, result);%0A        return result;%0A    %7D%0A%0A    private static void wordBreak(String s, Set%3CString%3E words, int i, int j, String accu,%0A                                  List%3CString%3E result) %7B%0A        if (j %3E s.length()) %7B%0A            if (i == s.length()) %7B%0A                result.add(accu);%0A            %7D%0A            return;%0A        %7D%0A        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%0A                newAccu += %22 %22 + sub;%0A            %7D%0A            wordBreak(s, words, j, j + 1, newAccu, result);%0A        %7D%0A        wordBreak(s, words, i, j + 1, accu, result)
 ;%0A  

Update problem 140