139. 单词拆分 - 力扣（LeetCode）
总结：自己一开始想的利用回溯来解决但是也考虑到可能会超时，从动归角度入手，自己没有弄清楚dp数组的含义而导致没有正确解决问题，此题的dp数组是当字符串的子串长度为i时，dp[i]表示能否用给定字典中的串表示出来，此题是一个排列的完全背包。文章来源：https://www.toymoban.com/news/detail-676660.html
代码：文章来源地址https://www.toymoban.com/news/detail-676660.html
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 temp = s.substr(j,i - j);
if(wordset.find(temp) != wordset.end() && dp[j] == true)
dp[i] = true;
}
}
return dp[s.size()];
}
};到了这里，关于算法训练第四十六天的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
