LeetCode 139 单词拆分
🟠 中等偏上
https://leetcode.cn/problems/word-break/description/
不好的思路：类似于换零钱问题，index遍历零钱。如果从字典中拿一个字符，能在主串中匹配，那么有选或不选两种可能，不匹配就不选。但是这样就要每次都要匹配一下，并且切割剩下的串不能合并，增加复杂程度。
好的思路：index遍历主串，把index前面的切下来，去字典中比较，匹配到就有两种选择，不匹配就直接不选。好像分割回文串的问题[分割回文串](../04 回溯/LeetCode 131 分割回文串 - 回溯解法.md)
根据 [分割回文串](../04 回溯/LeetCode 131 分割回文串 - 回溯解法.md) 写出本题递归代码
class Solution {
public:
bool del_word(string& s, int pre, unordered_set<string>& word_set) {
//如果左边分完了，返回true
if (pre == s.size()) {
return true;
}
for (int i = 1; pre + i <= s.size(); i++) {
//如果左边是集合中的一个，那么分割右边
if (word_set.count(s.substr(pre, i))) {
if (del_word(s, pre + i, word_set)) {
return true;
}
}
}
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
auto word_set = unordered_set<string>();
for (auto word : wordDict) {
word_set.insert(word);
}
return del_word(s,0,word_set);
}
};
改为动态规划
分析：递归输入是pre一位变量，因此dp为一维数组，因为pre从0到size，因此大小为size+1， 本层递归返回值依赖于很多 del_word(s，pre + i，word_set) 的返回值。这些的传入变量都比pre大，因此从大的向小的遍历。
class Solution {
public:
bool del_word(string& s, int pre, unordered_set<string>& word_set) {
if (pre == s.size()) {
return true;
}
for (int i = 1; pre + i <= s.size(); i++) {
if (word_set.count(s.substr(pre, i))) {
if (del_word(s, pre + i, word_set)) {
return true;
}
}
}
return false;
}
bool wordBreak(string s, vector<string>& wordDict) {
auto word_set = unordered_set<string>();
for (auto word : wordDict) {
word_set.insert(word);
}
vector<bool> dp(s.size() + 1, false);
dp[s.size()] = true;
for (int i = s.size() - 1; i >= 0; i--) {
for (int len = 1; i + len <= s.size(); len++) {
if (word_set.count(s.substr(i, len)) && dp[i + len]) {
dp[i] = true;
break;
}
}
}
// return del_word(s,0,word_set);
return dp[0];
}
};