力扣139-单词拆分（Java详细题解）

题目链接：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, List<String> wordDict) {//本题要求将背包装满，如果能装满返回true 不能装满返回false//利用一个hash结构来快速查找[j,i]只否能在wordDict中查到HashSet<String> 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数组推导的过程。

这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。

我很乐意为你解答。那么我们下篇再见！