17
06/2015
[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".
解题思路：
解法1，回溯法。但会超时。其时间复杂度为len!
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
return helper(s, wordDict);
}
bool helper(string s, unordered_set<string>& wordDict){
if(s==""){
return true;
}
int len = s.length();
for(int i=1; i<=len; i++){
if(wordDict.find(s.substr(0, i))!=wordDict.end() && helper(s.substr(i), wordDict)){
return true;
}
}
return false;
}
};解法2，动态规划。对于d[i]表示字符串S[0,..., i]费否能够被字典拼接而成。于是有
d[i] = true, 如果s[0,...i]在字典里面
d[i] = true, 如果存在k，0<k<i，且d[k]=true，s[k+1, .., i]在字典里面
d[i] = false, 不存在这样的k
代码如下：
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int len = s.length();
if(len == 0){
return true;
}
bool d[len];
memset(d, 0, len * sizeof(bool));
if(wordDict.find(s.substr(0, 1)) == wordDict.end()){
d[0] = false;
}else{
d[0] = true;
}
for(int i=1; i<len; i++){
for(int k=0; k<i; k++){
d[i] = wordDict.find(s.substr(0, i+1))!=wordDict.end() || d[k] && (wordDict.find(s.substr(k+1, i-k))!=wordDict.end());
if(d[i]){
break;
}
}
}
return d[len-1];
}
};时间复杂度为O(len^2)
另外，一个非常好的解法就是添加一个字符在s前面，使得代码更加简洁。
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
s = "#" + s;
int len = s.length();
bool d[len];
memset(d, 0, len * sizeof(bool));
d[0] = true;
for(int i=1; i<len; i++){
for(int k=0; k<i; k++){
d[i] = d[k] && (wordDict.find(s.substr(k+1, i-k))!=wordDict.end());
if(d[i]){
break;
}
}
}
return d[len-1];
}
};转载请注明：康瑞部落 » [LeetCode] Word Break
0 条评论