一、题目
题目链接:139. 单词拆分 - 力扣(LeetCode)
二、解题步骤
下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。
三、参考代码
文章来源:https://www.toymoban.com/news/detail-631323.html
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n=s.size();
vector<int> dp(n+1);
s=' '+s;
unordered_set<string> set;
for(const auto& e:wordDict)
{
set.insert(e);
}
dp[0]=true;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(dp[j-1]&&set.count(s.substr(j,i-j+1)))
{
dp[i]=true;
break;
}
else
{
dp[i]=false;
}
}
}
return dp[n];
}
};
以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心,点点关注呗,后期还会持续更新动态规划的经典题目哦,我们下期见啦!!!!! !!!!文章来源地址https://www.toymoban.com/news/detail-631323.html
到了这里,关于力扣 -- 139. 单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!