// Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. // For example, given var string = "leetcode", dict = ["leet", "code"]; // Return true because "leetcode" can be segmented as "leet code".

wordbreak1

// Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
// For example, given
var string = "leetcode",
	dict = ["leet", "code"];
// Return true because "leetcode" can be segmented as "leet code".

// 1. Naive Approach
// This problem can be solve by using a naive approach, which is trivial. A discussion can always start from that though.
// Time is O(n^2) and exceeds the time limit.
var wordBreak = function (string, dict) {
	return wordBreakHelper(string, dict, 0);
}

var wordBreakHelper = function (string, dict, start) {
    if (start === string.length) {
        return true;
    }

    for (var a in dict) {
        var len = dict[a].length,
        	end = start + len;

        //end index should be <= string length
        if (end > string.length) {
            continue;
        }

        if (string.substring(start, start + len) === dict[a]) {
            if (wordBreakHelper(string, dict, start + len)) {
                return true;
            }
        }
    }

    return false;
};
var string = "leetcode",
	dict = ["leet", "code"];

wordBreak(string, dict);

// 2. Dynamic Programming
// The key to solve this problem by using dynamic programming approach:
// Define an array t[] such that t[i]==true => 0-(i-1) can be segmented using dictionary
// Initial state t[0] == true
// Time: O(string length * dict size)
// One tricky part of this solution is the case:
// INPUT: "programcreek", ["programcree","program","creek"]. 
// We should get all possible matches, not stop at "programcree".
var wordBreak = function (string, dict) {
    var t = [string.length + 1];
        t[0] = true; //set first to be true, why?
        //Because we need initial state

    for (var i = 0; i < string.length; i++) {
        //should continue from match position
        if (!t[i]) {
            continue;
        }

        for (var a in dict) {
            var len = dict[a].length,
            	end = i + len;
            
            if (end > string.length) {
                continue;
            }

            if (t[end]) {
            	continue;
            }

            if (string.substring(i, end) === dict[a]) {
                t[end] = true;
            }
        }
    }

    return t[string.length];
};

var string = "leetcode",
	dict = ["leet", "code"];
console.log(wordBreak(string, dict));

var string = "programcreek",
	dict = ["programcree","program","creek"];
console.log(wordBreak(string, dict));


// 3. Regular Expression
// The problem is equivalent to matching the regular expression (leet|code)*,
// which means that it can be solved by building a DFA in O(2^m) and
// executing it in O(n). (Thanks to hdante.)
var wordBreak = function() {
	var dict, sb, pattern, re, match;
	
	dict = ["go", "goal", "goals", "special"]; 
	sb = "";
 
	for (var str in dict){
		sb += str + "|";
	}
 
	pattern = sb.substring(0, sb.length - 1);
	pattern = "(" + pattern + ")*";
	re = new RegExp(pattern);
	match = "goalspecial".match(re);
 
	if (match.length) {
		console.log("match");
	}
};
wordBreak();

// 4. The More Interesting Problem
// The dynamic solution can tell us whether the string can be broken to words, but can not tell us what words the string is broken to. So how to get those words?