140. Word Break II

LeetCode Link

题目：Given string and dictionary, 求取 breakable 的所有组合

思路：Divide and conquer

public ArrayList<String> wordBreak(String s, List<String> wordDict) {
    Map<String, ArrayList<String>> map = new HashMap<>();
    Set<String> dict = new HashSet<>(wordDict);
    
    return wordBreakHelper(s, dict, map);
}

// divide and conquer
private ArrayList<String> wordBreakHelper(String s, Set<String> dict, Map<String, ArrayList<String>> map) {
    if (map.containsKey(s)) {
        return map.get(s);
    }
    
    ArrayList<String> newList = new ArrayList<>();
    if (dict.contains(s)) {
        newList.add(s);
    }
    
    for (int i = 1; i < s.length(); i++) {
        String possibleWord = s.substring(0, i);
        if (dict.contains(possibleWord)) {
            ArrayList<String> wordsList = wordBreakHelper(s.substring(i), dict, map);
            for (String words: wordsList) {
                newList.add(possibleWord + " " + words);
            }
        }
    }
    
    map.put(s, newList);
    return newList;
}

求取所有组合，DP 并不适合这类题目。DP 适合的题目：

1. 是否存在解
2. 最大、最小
3. Count(*): Word Break 所有组合的数目，Word Break iii

Word Break III

LintCode Link

返回所有 break 方式的数量

dp[0][i] = sum(dp[0][j] * dp[j][i]) where j >= 0 && j < i

Solution Link

public int wordBreak3(String s, Set<String> dict) {
    int n = s.length();
    String lowerS = s.toLowerCase();
    
    Set<String> lowerDict = new HashSet<String>();
    for(String str : dict) {
        lowerDict.add(str.toLowerCase());
    }
    int[][] dp = new int[n][n];
    for(int i = 0; i < n; i++){
        for(int j = i; j < n;j++){
            String sub = lowerS.substring(i, j + 1);
            if(lowerDict.contains(sub)){
                dp[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            for(int k = i; k < j; k++){
                dp[i][j] += (dp[i][k] * dp[k + 1][j]);
            }
        }
    }
    return dp[0][n - 1];
}

根据上面的题解，我的题解：

    public int wordBreak3(String s, Set<String> wordDict) {
        s = s.toLowerCase();
        int len = s.length();
        
        Set<String> dict = new HashSet<>();
        for (String word: wordDict) {
            dict.add(word.toLowerCase());
        }
        
        int[][] dp = new int[len + 1][len + 1];
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                String possibleWord = s.substring(j, i);
                if (dict.contains(possibleWord)) {
                    dp[j][i] = 1;
                }
            }
        }
        
        // 尚未完成
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                dp[j][i] = 
            }
        }