电子商务网站规划方案,做民宿怎么登录网站,网页设计作业保护动物,网站后台做图片尺寸是多大题目链接#xff1a;139. 单词拆分 - 力扣#xff08;LeetCode#xff09;
前情提要#xff1a;
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完背包#xff0c;所以现在的题解都是以背包问题为基础再来写的。
如果大家不懂背包问题的话#…题目链接139. 单词拆分 - 力扣LeetCode
前情提要
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
最近刚学完背包所以现在的题解都是以背包问题为基础再来写的。
如果大家不懂背包问题的话建议可以去学一学01背包和完全背包。 如果大家感兴趣我后期可以出一篇专门讲解背包问题。 dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚那么这道题就能解出来了。 这里下文统一使用一维dp数组。 题目思路:
本题题目描述比较清晰给了我们一个非空字符串s和一个字符串列表wordDict作为字典要求我们利用wordDict里的字符串来拼接出s能拼接返回true,不能拼接返回false。wordDict中的字符串可以使用多次。
看完这个题目描述是不是能够联想到完全背包。
其实wordDict的字符串就可以抽象为完全背包问题中的物品s就是背包。
那么该题就可以转化为能不能将背包中的容量拆分拆分分配到各个物品上如果刚好能拆分完也就是看能不能将背包装满
但这里因为s是一个字符串所以我们用字符串的长度作为背包容量。
话不多说我们直接开始动规五部曲。
1.确定dp数组和i下标的含义。
我们最后结果要输出什么就怎么定义dp数组。
字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。
2.确定递推公式。
该题的递推公式与之前的有些不同之前的是把每一个物品装入到我们的背包中。
但该题因为是字符串装入有点难所以换一种思路我们将背包进行拆分将背包容量字符串s拆分为一个个物品wordDict字典里的字符串,如果能拆分成功就return true如果不能就return false。
如果此时我们的dp[j] 为 true的话那说明字符串长度为j的s是可以拆分为一个或者多个字典中出现的单词那么我们就只用再判断[j,i]这段区域是否也能拆分为字典中出现的单词如果能拆分那么dp[i]就为true。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
3.dp初始化。
本题的初始化不能从题目描述中得出。得从递推公式中推出。
有递推公式可以看出dp[i] 都是由 dp[j - i]推出所以我们当前的状态是由前面的状态推出。
那我们的dp[0]就必须初始化为true,如果初始化为false的话后面推出来的都是false。
4.确定dp的遍历顺序。
该题的遍历顺序也有一定讲究举个例子。
s leetcode, wordDict [leet, code]这个s只能先拆分为leet 再拆分为 code。换句话说s只能先由leet组成再加上code。所以该物品是有顺序的。
如果没有顺序那可能会组成codeleet这并不是我们要的结果。
在完全背包问题中先遍历物品后遍历背包求的是物品的组合。
先遍历背包后遍历物品求的是物品的排列。
组合是无顺序的排列是有顺序的所以本题要先先遍历背包后遍历物品。
5.如果没有ac打印dp数组 利于debug。 最终代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {//本题要求将背包装满如果能装满返回true 不能装满返回false//利用一个hash结构来快速查找[j,i]只否能在wordDict中查到HashSetString set new HashSet(wordDict);//定义dp数组boolean [] dp new boolean [s.length() 1];//dp初始化dp[0] true;//该题其实是求一个排列 所以需要先遍历背包 后遍历物品for(int i 1;i s.length();i ){for(int j 0;j i;j ){//我们要判断[j i]就是物品我们要判断该物品是否出现在我们的字典里if(set.contains(s.substring(j,i)) dp[j]){dp[i] true;}}}return dp[s.length()];}
}dp类的题目如果想加深理解我建议大家手动模拟一下dp数组推导的过程。
这一篇博客就到这了如果你有什么疑问和想法可以打在评论区或者私信我。
我很乐意为你解答。那么我们下篇再见
