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

$$f(i) = any\_of(f(j) \&\& s[j+1,i] \in dict), 0 \leq j < i$$

// 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;
}
};


// 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. 真要按你这么说的话，从甲骨文到繁体字都有人写，但是简体字一定没人写。（笑，中国那么多年封建社会一夫多妻，历代是底层文盲的早死光了。

2. 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.

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