北京西城区建设局网站,深圳做网站设计公司,易货网站开发,wordpress后台主题插件139. 单词拆分 - 力扣#xff08;LeetCode#xff09;
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1LeetCode
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以由 leet 和 code 拼接成。示例 2
输入: s applepenapple, wordDict [apple, pen]
输出: true
解释: 返回 true 因为 applepenapple可以由 apple pen apple 拼接成。注意你可以重复使用字典中的单词。
思路完全背包问题单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。转换成背包问题有两个难点①dp[i]是如何来的②遍历顺序。
解决动态规划五步曲 1.确定dp[j]的含义 dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。 2.确定dp[j]递推公式 这里递推公式好像和之前不同这里既没有01背包的价值又没有完全背包的组合数量通过dp[j]的含义我们知道dp[i]要不就是true要不就是false我们要的就是true。 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。 到这里有点懵了i是字符串长度那j是什么j这里其实表示当前遍历字符串中的位置。 举个例子s leet, wordDict [le, et] i等于1时j就从0开始j0时截取i-j就是le发现wordDict中有“le”所以dp[i]true。 3.确定dp初始化 没开始前dp[i]false但是从递推公式中可以看出dp[i] 的状态依靠 dp[j]是否为true那么dp[0]就是递推的根基dp[0]一定要为true否则递推下去后面都都是false了 4.确定遍历顺序 从上面分析可知随着字符串长度i增大依次遍历能在wordDict中找到的单词肯定越多结果也越有可能是true。所以本题一定是先遍历背包再遍历物品。 举个例子拿 s applepenapple, wordDict [apple, pen] 举例。 apple, pen 是物品那么我们要求 物品的组合一定是 apple pen apple 才能组成 applepenapple。apple apple pen 或者 pen apple apple 是不可以的那么我们就是强调物品之间顺序。 5.举例推导dp数组。 以输入: s leetcode, wordDict [leet, code]为例dp状态如图 代码这里利用unordered_set判断是否在wordDict中找到单词。
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {vectorbool dp(s.size()1,false);unordered_setstring wordSet(wordDict.begin(), wordDict.end());dp[0]true;for(int i0;is.size();i){for(int j0;ji;j){string word s.substr(j, i - j); //substr(起始位置截取的个数)if(wordSet.find(word) ! wordSet.end()dp[j]){//dp[j]表示前j个长度的字符串可以由单词拼接并且截取的子字符串在数组中dp[i]true;}}}return dp[s.size()];}
};
多重背包 例题有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。 区别多重背包和01背包是非常像的每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。 面试基本不会考了解即可。
背包问题总结
难点递推公式和遍历顺序
步骤
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
递推公式总结 1.问能否能装满背包或者最多装多少dp[j] max(dp[j], dp[j - nums[i]] nums[i]) 2. 问装满背包有几种方法dp[j] dp[j - nums[i]] 3.问背包装满最大价值dp[j] max(dp[j], dp[j - weight[i]] value[i]) 4.问装满背包所有物品的最小个数dp[j] min(dp[j - coins[i]] 1, dp[j])
遍历顺序总结 1.01背包 ①二维数组二维dp数组01背包先遍历物品还是先遍历背包都是可以的且第二层for循环是从小到大遍历。 ②一维数组一维dp数组01背包只能先遍历物品再遍历背包容量且第二层for循环是从大到小遍历。 2.完全背包 ①如果求组合数就是外层for循环遍历物品内层for循环遍历背包。 ②如果求排列数就是外层for循环遍历背包内层for循环遍历物品。
总结对于背包问题其实递推公式算是容易的难是难在遍历顺序上如果把遍历顺序搞透才算是真正理解了。
