140. Word Break II

This problem is similar to 45. Jump Game II. Whether current place is valid depends on the previous steps.

The basic idea is same with the previous problem 139. Word Break (my solution). We still use a array dp to denote whether substring of s can be segmented into words in wodDict. Besides, we use a list array prevIndex to help use generate all possible segmentation. If dp[i] is true then prevIndex[i] includes all valid index j where

1. 0 <= j < i;
2. dp[j] == true and
3. s.substring(j, i) exists in wordDict

We traverse s.substring(0, i) where 1 <= i <= s.length() to update dp[i] and preIndex[i]. If dp[s.length()] is false, then s can't be segmented into words in wordDict. If dp[s.length()] is true, then we backtrack prevIndex from index s.length() to 0 to generate all possible sentences.

public void generateResultList(List<String> resultList, StringBuilder sb, String s, List<Integer> prevIndex[], int index) {
    if( index == 0 )
	resultList.add(sb.substring(0, sb.length() - 1));
    else{
	int length = sb.length();
	for(int i = 0; i < prevIndex[index].size(); i++) {
	    sb.insert(0, " ");
	    sb.insert(0, s.substring(prevIndex[index].get(i), index));
	    generateResultList(resultList, sb, s, prevIndex, prevIndex[index].get(i));
	    sb = new StringBuilder(sb.substring(sb.length() - length, sb.length()));
	}    
    }
}

public List<String> wordBreak(String s, List<String> wordDict) {
    List<String> resultList = new ArrayList<String>();

    Set<String> wordSet = new HashSet<String>(wordDict);
    List<Integer> prevIndex[] = new List[s.length() + 1];
    for(int i = 0; i <= s.length(); i++)
	prevIndex[i] = new ArrayList<Integer>();
    boolean dp[] = new boolean[s.length() + 1];

    dp[0] = true;
    for(int i = 1; i <= s.length(); i++) {
	for(int j = 0; j < i; j++) {
	    if( dp[j] && wordSet.contains(s.substring(j, i)) ) {
		dp[i] = true;
		prevIndex[i].add(j);
	    }
	}
    }
    if( !dp[s.length()] )
	return resultList;
    else { // backtracking prevIndex to generate all sentences
	generateResultList(resultList, new StringBuilder(""), s, prevIndex, s.length());
	return resultList;
    }
}