139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
思路：
定义状态矩阵dp[i]表示0-i能被切割,需要先找到0-（j -1），然后j -i 这个区间是否是字典里面的，这样找。思路就是序列性动态规划，事件复杂度是n^2.
注意本题的初始化方法，需要从0开始进行查找符合条件的字典字符串，要找到从0位置开始的所有符合条件的字符串，比如go,goal,goals。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
if(s.size() == ){
return false;
}
if(wordDict.size() == ){
return ;
}
int n = s.size();
vector<bool> dp(n,false);
//hashset
unordered_set<string> wordSet;
for(int i = ;i < wordDict.size();++i){
wordSet.insert(wordDict[i]);
}
//find first true
int ix = ;
for(ix = ;ix < n;++ix){
if(wordSet.find(s.substr(,ix + )) != wordSet.end()){
dp[ix] = true;
//break;
}
}
// if(ix == n){
// return dp[ix - 1];
// }开始这里没注释，直接每次退出循环ix都等于n，总是出错，因为是原来break掉，才有这句
//funciton
for(int i = ;i < n;++i){
for(int j = ;j <= i;++j){
if((dp[j - ] == true) && (wordSet.find(s.substr(j,i - j + )) != wordSet.end())){
dp[i] = true;
}
}
}
return dp[n - ];
}
};
Word breakII需要找出所有符合条件的分割字符串，并且输出。首先考虑DFS模板，这里的巧妙之处就是start取代了j这个变量，但是复杂度还是平方级别。不熟悉的是string的append，insert，erase（pos,arg），记住是包含pos位置的。参考：水中的鱼
class Solution {
public:
void helper(unordered_set<string> &wordSet,vector<string> &res,string &s,string &tmp,int start){
if(start == s.size()){
res.push_back(tmp.substr(,tmp.size() - ));
}
for(int i = start;i < s.size();++i){
string sub = s.substr(start,i - start + );
if( wordSet.find(sub) == wordSet.end()){
continue;
}
tmp.append(sub).append(" ");//只有每步满足条件之后才开始位置为该步的下一步
helper(wordSet,res,s,tmp,i + );
tmp.erase(tmp.size() - sub.size() - );
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
if(s.size() == ){
return {};
}
if(wordDict.size() == ){
return {};
}
vector<string> res;
unordered_set<string> wordSet;
for(string tmp : wordDict){
wordSet.insert(tmp);
}
string tmp;
helper(wordSet,res,s,tmp,);
return res;
}
};
这样有很多重复计算，需要引入一个isOK矩阵，记录之前访问的结果，如果在之前i这个位置已经切割了一次，并且没有找到结果，那么就是false，下次不需要再访问了。这里首先都初始化为true。
int oldSize = res.size();
helper(wordSet,res,s,tmp,i + ,isOk);
if(oldSize == res.size()){
isOk[i] = false;
}
这里理解起来比较困难，记住每次经过helper函数应该是有一个结果压入res中的，但是前后size一样大，所以从i这个元素切割没有的得到结果，那下次切割到这个i的时候，就不需要再计算了，直接跳过。
class Solution {
public:
void helper(unordered_set<string> &wordSet,vector<string> &res,string &s,string &tmp,int start,vector<bool> &isOk){
if(start == s.size()){
res.push_back(tmp.substr(,tmp.size() - ));
}
for(int i = start;i < s.size();++i){
string sub = s.substr(start,i - start + );
if((isOk[i] == false) || wordSet.find(sub) == wordSet.end()){
continue;
}
tmp.append(sub).append(" ");//只有每步满足条件之后才开始位置为该步的下一步
int oldSize = res.size();
helper(wordSet,res,s,tmp,i + ,isOk);
if(oldSize == res.size()){
isOk[i] = false;
}
tmp.erase(tmp.size() - sub.size() - );
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
if(s.size() == ){
return {};
}
if(wordDict.size() == ){
return {};
}
vector<string> res;
unordered_set<string> wordSet;
for(string tmp : wordDict){
wordSet.insert(tmp);
}
string tmp;
vector<bool> isOk(s.size(),true);//代表从i位置分割是否能得到一个结果
//isOk[0] = false;
helper(wordSet,res,s,tmp,,isOk);
return res;
}
};