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

LeetCode-Word Break[动态规划]

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

标签: Dynamic Programming
分析

设状态为$f(i)$,表示{s[0,i]}是否可以分词,则状态转移方程为
$$
f(i) = any\_of(f(j) \&\& s[j+1,i] \in dict), 0 \leq j < i
$$

代码1

// LeetCode, Word Break
// 深搜,超时
// 时间复杂度O(2^n),空间复杂度O(n)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        return dfs(s, dict, 0, 0);
    }
private:
    static bool dfs(const string &s, unordered_set<string> &dict,
            size_t start, size_t cur) {
        if (cur == s.size()) {
            return dict.find(s.substr(start, cur-start+1)) != dict.end();
        }
        if (dfs(s, dict, start, cur+1)) return true;
        if (dict.find(s.substr(start, cur-start+1)) != dict.end())
            if (dfs(s, dict, cur+1, cur+1)) return true;
        return false;
    }
};

代码2

// LeetCode, Word Break
// 动规,时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        // 长度为n的字符串有n+1个隔板
        vector<bool> f(s.size() + 1, false);
        f[0] = true; // 空字符串
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[s.size()];
    }
};

Java代码:

public class Solution {
    static int dp[];
		static String string;
	 public static boolean wordBreak(String s, Set<String> dict) {
		 if(s==null || s.length()==0) return false;
        dp = new int[s.length()+1];
        string = s;
        return find(0, dict);
	  }
	 public static boolean find(int s, Set<String> set){
		  if(dp[s] == -1) return false;
        if( s == string.length() || dp[s] == 1) return true;
        // System.out.println(s);
        String tmpstr = string.substring(s,string.length());
        //System.out.println(tmpstr);
        boolean find = false;
        for(String str:set){
            if(tmpstr.startsWith(str)){
                find =  find(s+str.length(), set);
            }
            if(find){
                dp[s] = 1;
                return true;
            }
        }
        dp[s] = -1;
        return false;
	 }
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。