139.单词拆分
没想到怎么用动态规划去写，看题解说回溯算法也能做，就自己写了回溯算法的。但是超时了。
class Solution {
public:
static bool cmp(string a, string b){
if(a.length() < b.length())
return true;
return false;
}
bool found = false;
void backtracking(string s, vector<string>& wordDict, string cur){
if(s.compare(cur) == 0){
found = true;
return ;
}
for(int i=0; i<wordDict.size() && !found; i++){
int pre_size = cur.length();
string temp = cur + wordDict[i];
if(temp.size() <= s.length())
backtracking(s,wordDict,temp);
temp.substr(0,pre_size);
}
}
bool wordBreak(string s, vector<string>& wordDict) {
string empty_str = "";
sort(wordDict.begin(),wordDict.end(),cmp);
return found;
}
};
也明白了动态规划的该怎么写，但自己写的就是不对
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1,false);
dp[0] = true;
for(int i=1; i<=s.size(); i++){
for(int j=0; j<wordDict.size(); j++){
int break_point = i - wordDict[j].length();
int sub_start = break_point;
int sub_end = wordDict[j].length();
if(break_point >= 0){
cout<<break_point<<" "<< wordDict[j]<<" "<<s.substr(sub_start,sub_end)<<endl;
bool first_part = dp[break_point];
bool second_part = wordDict[j].compare(s.substr(sub_start,sub_end));
cout<<first_part<<" "<<!second_part<<endl;
dp[i] = first_part && !second_part;
//cout<<dp[i]<<endl;
}
}
for(int m=0; m<=s.size();m++){
//cout<<dp[m]<<" ";
}
cout<<endl;
}
return dp[s.length()];
}
};
答案是这么写的。思路其实和我刚才理解的还是稍微有些区别。
首先把dp[0]初始化成true这点我想到了。但是Carl是外循环遍历s，把s从最小的位置开始开始和wordDict进行比较，有的话，那就把dp[i]写成true。
与其说是j用来遍历物品，不如说j是用来分割s，然后把substring的值与wordDict比较。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); i++) { // 遍历背包
for (int j = 0; j < i; j++) { // 遍历物品
string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
if (wordSet.find(word) != wordSet.end() && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
