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"], the solution is ["cats and dog", "cat sand dog"].

wordbreak2

// 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"], the solution is ["cats and dog", "cat sand dog"].

// need to track the actual matched words
var wordBreak = function (string, dict) {
    //create an array of ArrayList<String>
    var dp = [string.length + 1];
    dp[0] = [];
 
    for (var i = 0; i < string.length; i++) {
        if (dp[i] == null) {
            continue; 
        } 
 
        for (var word in dict) {
            var len = dict[word].length;
            var end = i + len;
            if (end > string.length) {
                continue;
            } 
 
            if (string.substring(i, end) === dict[word]) {
                if (dp[end] == null) {
                    dp[end] = [];
                }
                dp[end].push(dict[word]);
            }
        }
    }
 
    var result = [];
    if (dp[string.length] == null) {
        return result; 
    } 
 
    var temp = [];
    dfs(dp, string.length, result, temp);
 
    return result;
}
 
var dfs = function(dp, end, result, tmp) {
    if (end <= 0) {
        var path = tmp[tmp.length - 1];
        for (var i = tmp.length - 2; i >= 0; i--) {
            path += " " + tmp[i];
        }
 
        result.push(path);
        return;
    }
 
    for (var str in dp[end]) {
        tmp.push(dp[end][str]);
        dfs(dp, end - dp[end][str].length, result, tmp);
        tmp.splice(tmp.length - 1, 1);
    }
};

var str, dict;
str = "catsanddog";
dict = ["cat", "cats", "and", "sand", "dog"];
wordBreak(str, dict);