美文网首页
代码随想录算法训练营第四十五天|139.单词拆分

代码随想录算法训练营第四十五天|139.单词拆分

作者: eagleX | 来源:发表于2023-09-21 21:45 被阅读0次

139.单词拆分

转化为背包问题:

单词就是物品,字符串s就是背包

动规五部曲

确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词

确定递推公式

如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true

dp[i] = true

dp数组初始化

dp[0]初始为true

确定遍历顺序

先遍历 背包,再遍历物品

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(inti=1;i<=s.size();i++){// 遍历背包for(intj=0;j<i;j++){// 遍历物品string word=s.substr(j,i-j);//substr(起始位置,截取的个数)if(wordSet.find(word)!=wordSet.end()&&dp[j]){dp[i]=true;}}}returndp[s.size()];}

相关文章

网友评论

      本文标题:代码随想录算法训练营第四十五天|139.单词拆分

      本文链接:https://www.haomeiwen.com/subject/obbzvdtx.html