Word Break II (not finished yet....)

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

Solution1: brute force，DFS recursion（在leetcode上超时）

要返回所有合法结果，一般来说这种要求会让动态规划的效果减弱很多，因为要在过程中记录下所有的合法结果，中间的操作会使得算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面需要历史信息会取不到。

brute force， 每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList res = new ArrayList();
        if(s == null || s.length() == 0) {
            return res;
        }
        
        helper(s, dict, 0, "", res);
        return res;
    }
    
    public void helper(String s, Set dict, int start, String item, ArrayList res) {
        if(start >= s.length()) {
            res.add(item);
            return;
        }
        
        StringBuilder str = new StringBuilder();
        for(int i = start; i < s.length(); i++) {
            str.append(s.charAt(i));
            if(dict.contains(str.toString())) {
                String newItem = new String();
                if(item.length() == 0) {
                    newItem = str.toString();
                }else {
                    newItem = item + " " + str.toString();
                }
                helper(s, dict, i + 1, newItem, res);
            }
        }
    }
}

Reference:http://blog.csdn.net/linhuanmars/article/details/22452163