第九章 动态规划part08

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

关于字符串类型的题目还是很不熟悉，重新回顾了之前写过的131. 分割回文串使用回溯法解决。

已经忘记了字典需要先转化为unordered_set<string>，从而可以直接在其中find单词。

使用回溯法解决本题部分案例无法通过，使用动态规划：

注意递推公式推导。

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 word=s.substr(j,i-j);if(wordSet.find(word)!=wordSet.end()&&dp[j]){dp[i]=true;}}}return dp[s.size()];}
};

二刷字符串问题要重点掌握。

多重背包

多一个for循环遍历物品个数

背包总结

代码随想录