一个具体网站的seo优化方案,江西住房与城乡建设厅网站,哈尔滨香坊区地图,wordpress 嵌套评论139. 单词拆分#xff08;中等#xff09; 思路 首先将大问题分解成小问题#xff1a; 前 i 个字符的子串#xff0c;能否分解成单词#xff1b;剩余子串#xff0c;是否为单个单词#xff1b; 动态规划的四个步骤#xff1a; 确定 dp 数组以及下标的含义 dp[i] 表示 s…139. 单词拆分中等 思路 首先将大问题分解成小问题 前 i 个字符的子串能否分解成单词剩余子串是否为单个单词 动态规划的四个步骤 确定 dp 数组以及下标的含义 dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。 确定递推公式 如果 dp[j] true且 [j, i] 这个区间的子串出现在字典里那么 dp[i] 一定是true。 所以可以确定递推公式if([j,i] 这个区间的子串出现在字典里 dp[j] true) dp[i] true; dp 数组初始化 从递归公式中可以看出 dp[i] 的状态依靠 dp[j] 是否为 true那么 dp[0] 就是递归的根基令 dp[0] true 因为空字符串一定可以被表示 确定遍历顺序 题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包问题需要讨论两层 for 循环的前后顺序。 本周小结动态规划系列五 如果求组合数就是外层 for 循环遍历物品内层 for 循环遍历背包 如果求 排序数就是外层 for 循环遍历背包内层 for 循环遍历物品。 由于本题要求的是是否都出现过因此对单词集合里的元素是组合还是排序并不在意那么本题使用哪一种方法都可以。 但本题存在特殊性因为要求的是子串所以最好是遍历背包放在外层循环遍历物品放在内层循环。如果相反的话需要将所有子串预先放在一个容器里比较麻烦。 代码 class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {int n s.size();unordered_setstring WordSet(wordDict.begin(), wordDict.end());vectorbool dp(n1, false);dp[0] true; // 初始状态for(int i1; in; i){for(int j0; ji; j){string word s.substr(j, i-j); // (起始位置长度)if(WordSet.find(word) ! WordSet.end() dp[j]){dp[i] true;}}}return dp[n];}
};收获 总感觉之前做过类似的题不过不是使用动态规划的解法。这道题完全没思路找了很多题解才明白最后参考的是代码随想录的解法。
