I
title:
https://leetcode.com/problems/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"
.
思路:一开始就考虑直接使用dfs超时了。。。
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
if (s.size() == )
return true;
string tmp;
for (int i = ; i < s.size(); i++){
tmp.push_back(s[i]);
if (wordDict.find(tmp) != wordDict.end()){
string tmp1(s.begin()+i+,s.end());
if (wordBreak(tmp1,wordDict))
return true;
}
}
return false;
}
};
其实对于这样的问题,是可以想到是可以使用动态规划的。
一个DP问题。定义possible[i] 为S字符串上[0,i]的子串是否可以被segmented by dictionary.
那么
possible[i] = true if S[0,i]在dictionary里面
= true if possible[k] == true 并且 S[k+1,j]在dictionary里面, 0<k<i
= false if no such k exist.
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int len = s.size();
vector<bool> dp(len+,false);
dp[] = true;
for (int i = ; i < len+; i++){
for (int k = ; k < i; k++){
if (dp[k] && wordDict.find(s.substr(k,i-k)) != wordDict.end()){
dp[i] = true;
break;//break是因为题目只是需要判断是否存在
}
}
}
return dp[len];
}
};
II
https://leetcode.com/problems/word-break-ii/
title:
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,并且保存中间结果。注意,在I中找到一个解就直接break,这里需要记录下这个信息。另外prev[i][j]为true表示字串[j,i]在字典中
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) { int len = s.size();
vector<bool> dp(len+,false);
vector<vector<bool> > prev(len+,vector<bool>(len,false));
dp[] = true;
for (int i = ; i < len+; i++){
for (int k = ; k < i; k++){
if (dp[k] && wordDict.find(s.substr(k,i-k)) != wordDict.end()){
dp[i] = true;
prev[i][k] = true;
}
}
}
vector<string> result;
vector<string> results;
genPath(len,s,dp,prev,result,results);
return results;
} void genPath(int cur,string s, vector<bool> dp,vector<vector<bool> > prev, vector<string> &result,vector<string> &results){
if (cur == ){
string tmp;
for (int i = result.size()-; i > ; i--){
tmp += result[i] + " ";
}
tmp += result[];
results.push_back(tmp);
return ;
}
for (int i = ; i < s.size(); i++){
if (prev[cur][i]){
result.push_back(s.substr(i,cur-i));
genPath(i,s,dp,prev,result,results);
result.pop_back();
}
}
}
};