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.

Example

Gieve s =lintcode,
dict =["de", "ding", "co", "code", "lint"].

A solution is["lint code", "lint co de"].

Solution 1: DFS. TLE

public List<String> wordBreak(String s, Set<String> wordDict) {
    List<String> res = new ArrayList<String>();
    if(s == null || s.length() == 0) {
        return res;
    }
    List<String> item = new ArrayList<String>();
    dfs(s, wordDict, res, sb, 0);
    return res;
}
public void dfs(String s, Set<String> wordDict, List<String> res, List<String> item, int index) {
    if(index == s.length()) {
        StringBuilder sb = new StringBuilder();
        for(String ss : item) {
            sb.append(ss).append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        res.add(sb.toString());
    }
    for(int i = index; i < s.length(); i++) {
        String str = s.substring(index, i + 1);
        if(wordDict.contains(str)) {
            item.add(str);
            dfs(s, wordDict, res, sb, i + 1);
            item.remove(item.size() - 1);
        }
    }
}

Solution 2: DP with memory.

public List<String> wordBreak(String s, Set<String> wordDict) {
    List<String> res = new ArrayList<String>();
    if(s == null || s.length() == 0) {
        return res;
    }
    List<String> item = new ArrayList<String>();
    boolean[] dp = isBreak(s, wordDict);
    dfs(s, wordDict, res, item, 0, dp);
    return res;
}

public void dfs(String s, Set<String> wordDict, List<String> res, List<String> item, int index, boolean[] dp) {
    if(index == s.length()) {
        StringBuilder sb = new StringBuilder();
        for(String ss : item) {
            sb.append(ss).append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        res.add(sb.toString());
    }
    if(!dp[s.length()]) {
        return ;
    }
    for(int i = index; i < s.length(); i++) {
        String str = s.substring(index, i + 1);
        if(wordDict.contains(str)) {
            item.add(str);
            dfs(s, wordDict, res, item, i + 1, dp);
            item.remove(item.size() - 1);
        }
    }
}

public boolean[] isBreak(String s, Set<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= i; j++) {
            if(dp[j] && wordDict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp;
}