Word Break II

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

Solution 1
A straightforward way is to get all solutions by backtracking the DP table. As follows: 

	public ArrayList<String> wordBreak(String s, Set<String> dict) {
	ArrayList<String> ret = new ArrayList<String>();
	boolean [] dpb = new boolean[s.length()+1];
	String oneSolution = "";
	dpb[0] = true;
	for(int i =0; i < s.length(); i++){
	for(int j=i; j>=0; j--){
	if(dpb[j] == true){
	String tempStr = s.substring(j, i+1);
	for(String str : dict){
	if(str.equals(tempStr))
	dpb[i+1] = true;
	}
	}
	}
	}
	if(dpb[s.length()]==true){
	backTrack(0, dpb, s, dict, ret, oneSolution);
	return ret;
	}
	else return ret;
	}
	public void backTrack(int start, boolean[] dp, String s, Set<String> dict, ArrayList<String> ret, String oneSol){
	if(start == s.length()){//implies dp[s.length]==true
	ret.add(oneSol);
	return;
	}
	for(int i=start; i<=s.length(); i++){
	if(dp[i]==true){//find a breakable point from start->i-1 and
	String str = s.substring(start, i);
	if(dict.contains(str)){
	String tempStr = oneSol;
	if(start==0) tempStr+=str;
	else tempStr+= " " + str;
	backTrack(i, dp, s, dict, ret, tempStr);
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

test

view raw gistfile2.txt hosted with ❤ by GitHub

However, it cannot pass the large cases.

Got another way to solve this by mingling DP and Backtrack. Slight changes to the above code will pass all test cases.

	public ArrayList<String> wordBreak(String s, Set<String> dict) {
	ArrayList<String> ret = new ArrayList<String>();
	boolean [] dpb = new boolean[s.length()+1];
	String oneSolution = "";
	dpb[0] = true;
	for(int i =0; i < s.length(); i++){
	for(int j=i; j>=0; j--){
	if(dpb[j] == true){
	String tempStr = s.substring(j, i+1);
	for(String str : dict){
	if(str.equals(tempStr))
	dpb[i+1] = true;
	}
	}
	}
	}
	if(dpb[s.length()]==true){
	backTrack(0, dpb, s, dict, ret, oneSolution);
	return ret;
	}
	else return ret;
	}
	public void backTrack(int start, boolean[] dp, String s, Set<String> dict, ArrayList<String> ret, String oneSol){
	if(start == s.length()){//implies dp[s.length]==true
	ret.add(oneSol);
	return;
	}
	for(int i=start; i<=s.length(); i++){
	if(dp[i]==true){//find a breakable point from start->i-1 and
	String str = s.substring(start, i);
	if(dict.contains(str)){
	String tempStr = oneSol;
	if(start==0) tempStr+=str;
	else tempStr+= " " + str;
	backTrack(i, dp, s, dict, ret, tempStr);
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub