一开始，我有一个很简单的想法。
思路分析：
- 使用动态规划，初始化一个长度为
len + 1的dp数组，其中dp[i]表示字符串s的前i个字符是否可以被成功拆分。 - 使用
unordered_set存储wordDict中的单词，以提高查找效率。 - 外层循环遍历字符串
s，内层循环遍历wordDict中的单词。 - 对于每个位置
i，首先将dp[i]初始化为前一个位置的值。然后，对于每个单词，检查从dp[i]到i-1的子串是否在wordSet中。如果找到匹配的单词，更新dp[i]为当前位置i，并且可以提前结束内层循环。 - 最终判断
dp[len]是否等于len，如果是，则整个字符串可以被成功拆分，返回true，否则返回false。
class Solution {
public:
// 函数用于判断字符串 s 是否能够被拆分成 wordDict 中的单词
bool wordBreak(string s, vector<string>& wordDict) {
// 获取字符串 s 的长度
int len = s.size();
// dp 数组用于存储每个位置是否能够被成功拆分
vector<int> dp(len + 1, 0);
// 使用 unordered_set 存储 wordDict 中的单词，以提高查找效率
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
// 循环遍历字符串 s
for (int i = 1; i <= len; i++) {
// 初始化 dp[i] 为前一个位置的值
dp[i] = dp[i - 1];
// 遍历 wordDict 中的单词
for (int j = 0; j < wordDict.size(); j++) {
// 获取子串 s[dp[i]...i-1]
string currentWord = s.substr(dp[i], i - dp[i]);
// 如果当前子串在 wordSet 中，则更新 dp[i] 为当前位置 i
if (wordSet.count(currentWord) == 1) {
dp[i] = i;
break;
}
}
}
// 如果 dp[len] 等于 len，表示整个字符串可以被成功拆分
return dp[len] == len;
}
};看似很天衣无缝，非常简单吧，但是示例没有过。
s ="aaaaaaa"
wordDict =["aaaa","aaa"]
输出 false
预期结果 true
这个示例中，我们会重复找到aaa两次，让我们的dp变成dp[6]=6（aaaaaa)，而导致找不到那一个a导致输出false。但其实aaaa+aaa=aaaaaaa结果应该位true的。
那么该怎么解决这个问题呢？？？
思路分析：
- 使用动态规划来解决问题，其中 dp[i] 表示字符串 s 的前 i 个字符是否能够被拆分成 wordDict 中的单词组合。
- 初始化 dp[0] 为 true，表示空字符串可以被拆分。
- 通过两层循环遍历字符串 s 和每个可能的子串，判断当前子串是否在 wordDict 中，并且前面的部分 dp[j] 也为 true。
- 如果满足条件，更新 dp[i] 为 true，表示当前字符串可以被拆分成 wordDict 中的单词组合。
- 最终返回 dp[s.size()]，即整个字符串 s 是否能够被拆分成 wordDict 中的单词组合。
class Solution {
public:
// 函数用于判断字符串 s 是否能够被拆分成 wordDict 中的单词组合
bool wordBreak(string s, vector<string>& wordDict) {
// 将单词列表转换为无序集合，以便快速查找
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
// dp 数组，dp[i] 表示字符串 s 的前 i 个字符是否能够被拆分成 wordDict 中的单词组合
vector<bool> dp(s.size() + 1, false);
// 初始化，空字符串可以被拆分
dp[0] = true;
// 遍历字符串 s 中的每个字符
for (int i = 1; i <= s.size(); i++) {
// 遍历字符串 s 中从开头到当前字符的所有可能子串
for (int j = 0; j < i; j++) {
// 判断 s.substr(j, i - j) 是否在 wordSet 中，并且 dp[j] 为 true
// 如果是，表示当前子串可以被拆分成 wordDict 中的单词组合
if (wordSet.count(s.substr(j, i - j)) && dp[j]) {
dp[i] = true; // 更新 dp[i] 为 true
break; // 跳出内层循环，无需继续判断当前子串的其他可能性
}
}
}
// 返回整个字符串 s 是否能够被拆分成 wordDict 中的单词组合
return dp[s.size()];
}
};
※优化的关键：
&& dp[j] 这一步的目的是确保当前子串的前面部分也可以被拆分成 wordDict 中的单词组合。在动态规划的过程中，通过 dp[j] 的值来判断子串 s.substr(j, i - j) 的前半部分是否满足条件。
具体来说，对于当前的子串 s.substr(j, i - j)，程序会检查这个子串是否在 wordDict 中，即 wordSet.count(s.substr(j, i - j)) 是否为真。如果这个子串在 wordDict 中，说明当前部分是一个合法的单词。
然而，为了确保整个字符串 s 能够被拆分，还需要判断前面的部分 s.substr(0, j) 是否也能被拆分成 wordDict 中的单词组合，即 dp[j] 是否为真。如果前面的部分不能被拆分，那么即使当前部分是一个合法的单词，整个字符串仍然不能被拆分。文章来源：https://www.toymoban.com/news/detail-830291.html
因此，&& dp[j] 的条件是为了确保当前子串的前面部分也是合法的，从而综合考虑整个字符串的拆分情况。文章来源地址https://www.toymoban.com/news/detail-830291.html
到了这里，关于力扣--动态规划139.单词的拆分的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
