昆明新建设电影院网站,wordpress评论高亮,建设企业网站企业网上银行官网官方,网络软件开发day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分
题目链接 解题思路#xff1a;单词就是物品#xff0c;字符串s就是背包#xff0c;单词能否组成字符串s#xff0c;就是问物品能不能把背包装满。…
day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分
题目链接 解题思路单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词说明就是一个完全背包
动规五部曲分析如下
1.确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。
2.确定递推公式
如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
3.dp数组如何初始化
从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了。
那么dp[0]有没有意义呢
dp[0]表示如果字符串为空的话说明出现在字典里。
但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况那么dp[0]初始为true完全就是为了推导公式。
下标非0的dp[i]初始化为false只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
4.确定遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。
还要讨论两层for循环的前后顺序。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
做一个总结
而本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。
“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。
“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。
所以说本题一定是 先遍历 背包再遍历物品。
5.举例推导dp[i]
以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图 dp[s.size()]就是最终结果。 动规五部曲分析完毕C代码如下
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool 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); //substr(起始位置截取的个数)if (wordSet.find(word) ! wordSet.end() dp[j]) {dp[i] true;}}}return dp[s.size()];}
};
