首页 > 动态规划 > 线性DP > LeetCode-Word Break II[动态规划]
2014
11-19

LeetCode-Word Break II[动态规划]

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

标签: Dynamic Programming Backtracking
分析

在上一题的基础上,要返回解本身。

代码1

// LeetCode, Word Break II
// 动规,时间复杂度O(n^2),空间复杂度O(n^2)
class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // 长度为n的字符串有n+1个隔板
        vector<bool> f(s.length() + 1, false);
        // prev[i][j]为true,表示s[j, i)是一个合法单词,可以从j处切开
        // 第一行未用
        vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length()));
        f[0] = true;
        for (size_t i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    f[i] = true;
                    prev[i][j] = true;
                }
            }
        }
        vector<string> result;
        vector<string> path;
        gen_path(s, prev, s.length(), path, result);
        return result;

    }
private:
    // DFS遍历树,生成路径
    void gen_path(const string &s, const vector<vector<bool> > &prev,
            int cur, vector<string> &path, vector<string> &result) {
        if (cur == 0) {
            string tmp;
            for (auto iter = path.crbegin(); iter != path.crend(); ++iter)
                tmp += *iter + " ";
            tmp.erase(tmp.end() - 1);
            result.push_back(tmp);
        }
        for (size_t i = 0; i < s.size(); ++i) {
            if (prev[cur][i]) {
                path.push_back(s.substr(i, cur - i));
                gen_path(s, prev, i, path, result);
                path.pop_back();
            }
        }
    }
};

Java代码:

public class Solution {
   public static List<String> wordBreak(String s, Set<String> dict) {
        List<String> dp[] = new ArrayList[s.length()+1];
        dp[0] = new ArrayList<String>();
        for(int i=0; i<s.length(); i++){
            //i是开始位置
            if( dp[i] == null ) continue; //前面的部分必须是可以匹配的
            for(String word:dict){
                int len = word.length();
                int end = i+len;
                if(end > s.length()) continue;

                if(s.substring(i,end).equals(word)){
                    if(dp[end] == null){
                        dp[end] = new ArrayList<String>();
                    }
                    dp[end].add(word);//记录上一个位置
                }
            }
        }
        
        List<String> ans = new LinkedList<String>();
        if(dp[s.length()] == null) return ans; 
        ArrayList<String> tmp = new ArrayList<String>();
        dfsStringList(dp,s.length(),ans, tmp);
        return ans;
    }

    public static void dfsStringList(List<String> dp[],int end,List<String> res, ArrayList<String> tmp){
        if(end <= 0){
            String ans = tmp.get(tmp.size()-1);
            for(int i=tmp.size()-2; i>=0; i--)
                ans += (" " + tmp.get(i) );
            res.add(ans);
            return;
        }
        for(String str:dp[end]){
            tmp.add(str);
            dfsStringList(dp,end-str.length(), res, tmp);
            tmp.remove(tmp.size()-1);
        }

    }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮