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

 [分析]  最能感受dp剪枝好处的例子：

s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", 

dict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa",

"aaaaaaaaa","aaaaaaaaaa"]

 

//////////////////method 3////////////////////
    //tag: dp + dfs/backtracking/recursion
    //dp[i] means s.substring(i, N) satisfy wordBreak
    //dp[i] |= s.substring(i, j) && dp[j], i < j <=N
    public List<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if (dict == null || dict.size() == 0 || s == null || s.length() == 0)
            return result;
        int N = s.length();
        boolean[] dp = new boolean[N + 1];
        dp[N] = true;
        for (int i = N - 1; i >= 0; i--) {
            StringBuilder sub = new StringBuilder(s.substring(i, N));
            for (int j = N; j >= i; j--) {
                //dp[i]: s.sub(i, N), sub: s.sub(i, j), dp[j]: s.sub(j, N)
                dp[i] = dp[j] && dict.contains(sub.toString());
                if (dp[i])
                    break;
                if (j > i)
                    sub.deleteCharAt(sub.length() - 1);
            }
        }
        if (dp[0]) {
            StringBuilder item = new StringBuilder();
            recur(s, dict, 0, dp, item, result);
        }
        return result;
    }
    // 使用dp[]进行剪枝, dfs/backtracking/recursion
    // item = s.sub(0, beg)
    public void recur(String s, Set<String> dict, int beg, boolean[] dp, StringBuilder item, ArrayList<String> result) {
        if (beg == s.length()) {
            item.deleteCharAt(item.length() - 1);
            result.add(item.toString());
            return;
        }
        for (int i = beg + 1; i <= s.length(); i++) {
            String sub = s.substring(beg, i);
            if(dict.contains(sub)&& dp[i]) {
                int oldLength = item.length();
                item.append(sub).append(' ');
                recur(s, dict, i, dp, item, result);
                item.delete(oldLength, item.length());
            }
        }
    }
    
    /////////////////////method 2////////////////////
    /* Time Limit Exceeded
    public List<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0)
            return result;
        int N = s.length();
        boolean[] dp = new boolean[N + 1];
        ArrayList<ArrayList<StringBuilder>> data = new ArrayList<ArrayList<StringBuilder>>(N + 1);
        dp[0] = true;
        ArrayList<StringBuilder> data0 = new ArrayList<StringBuilder>();
        data0.add(new StringBuilder());
        data.add(data0);
        for (int i = 1; i <= N; i++) {
            data.add(new ArrayList<StringBuilder>());
            StringBuilder sub = new StringBuilder(s.substring(0, i));
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(sub.toString())) {
                    dp[i] = true;
                    for (StringBuilder sb : data.get(j)) {
                        StringBuilder copy = new StringBuilder(sb.toString());
                        copy.append(sub.toString()).append(' ');
                        data.get(i).add(copy);
                    }
                }
                sub.deleteCharAt(0);
            }
        }
        for (StringBuilder sb : data.get(N)) {
            sb.deleteCharAt(sb.length() - 1);
            result.add(sb.toString());
        }
        return result;
    }
    */
    
    //////////////////method 1/////////////////////
    /* Time Limit Exceeded
    public List<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if(s == null || s.length() == 0)
            return result;
        recur(s, dict, 0, new StringBuilder(), result);
        return result;
    }
    
    // 太多冗余计算
    public void recur(String s, Set<String>dict, int start, StringBuilder item, ArrayList<String> result) {
        if(start == s.length()) {
            item.deleteCharAt(item.length() - 1);
            result.add(item.toString());
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (dict.contains(sub)) {
                int oldLength = item.length();
                item.append(sub).append(' ');
                recur(s, dict, i + 1, item, result);
                int newLength = item.length();
                item.delete(oldLength, newLength);
            }
        }
    }
    */
    
}

 

评论

2 楼 likesky3 2015-04-16  

再复习的时候一开始想到仍然是原始的DFS，即使知道用DP来剪枝，仍不知如何下手。这道题目需要反复理解消化。

1 楼 qb_2008 2015-04-14  

第一种是DFS，超时很正常。
第二种是动态规划+记录解空间，竟然还超时，说明中间无效的解空间太庞大了。
第三种先动态规划，然后由dp状态只计算正确的解空间，算法书上算最长公共子序列
的解空间就是这样做的。值得学习！