动态规划|115、完全背包-LeetCode-139.单词拆分动态规划|算法|leetcode

题目：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
来源：力扣（LeetCode）
思路：
优化：因为进行判断时，不用从头开始，效率会很差！
可以记录字典中最长字串的长度，从后往前找，当要匹配的子串长度已经大于最长子串的长度了，肯定就不会成功，结束即可！
1）一个重要的点：对字典是否包含某段，自己的第一想法是不好判断，要组新的字符串；
但是最方便的解法是：使用substring()方法，使用下标获取字串，然后进行判断！
2）对于背包容量在外，物品在内的理解：
如果物品在外，按照之前的背包问题！字典中的字串每次循环，只加进来一个；
之前的思路是：如果只有该元素之前的元素，判断怎么组成最后的结果，要的是结果数；
这次只判断是否可以，就一个结果，是与否！
物品在内，每次判断字串时，就将字典中的所有结果拿来进行比较；更容易得到是或者否的结果！
其实最后都是一样的循环，感觉时间复杂度并不会有很高的提升！
总的来说，感觉思路固定，不是很难！
代码：
3）进一步优化：时间复杂度为O(N * M)
一样的判定条件：

for(int i = 1; i <= n; i++){ for(int j = Math.max(i - maxLength,0); j < i; j++ )

class Solution { public boolean wordBreak(String s, List wordDict) { //List默认没有存重复的字符串，contains就可以判断，和集合Set是一样的 int n = s.length(); int maxLength = 0; //记录字典中字符串最大长度！ boolean dp[] = new boolean[n + 1]; //dp数组代表的是，到该下标处(+1)处的字符串是否可以拼接 Set wordDictSet = new HashSet(wordDict); //优化：因为不需要每次都从最开始的位置进行判断：可以优化 for(String str : wordDict){ maxLength = Math.max(maxLength,str.length()); }dp[0] = true; //初始化 for(int i = 1; i <= n; i++){//背包容量，可以取到n，因为子串获取是左闭右开 for(int j = i; j >= 0 && j >= i - maxLength; j-- ){//对字典里的子串进行比较//感觉这里可以优化：contains附带了一个O(N)的时间复杂度 if(dp[j] == true && wordDictSet.contains(s.substring(j,i))){ //之前有包括的子串，且后面的位置，也被包括，就赋值为true dp[i] = true; //赋值为true，就可以跳出 break; } } } return dp[n]; } }

1）完全背包 + 背包容量在外，物品在内：O(N三次方)，因为List查找是O(N)的

class Solution { public boolean wordBreak(String s, List wordDict) { //List默认没有存重复的字符串，contains就可以判断，和集合Set是一样的 int n = s.length(); boolean dp[] = new boolean[n + 1]; //dp数组代表的是，到该下标处(+1)处的字符串是否可以拼接 dp[0] = true; //初始化 for(int i = 1; i <= n; i++){//背包容量，可以取到n，因为子串获取是左闭右开 for(int j = 0; j <= i; j++ ){//对字典里的子串进行比较//感觉这里可以优化：contains附带了一个O(N)的时间复杂度 if(dp[j] == true && wordDict.contains(s.substring(j,i))){ //之前有包括的子串，且后面的位置，也被包括，就赋值为true dp[i] = true; //赋值为true，就可以跳出 break; } } } return dp[n]; } }

2）使用Set优化复杂度，因为Set查找是 O(1)

class Solution { public boolean wordBreak(String s, List wordDict) { //List默认没有存重复的字符串，contains就可以判断，和集合Set是一样的 int n = s.length(); boolean dp[] = new boolean[n + 1]; //dp数组代表的是，到该下标处(+1)处的字符串是否可以拼接 Set wordDictSet = new HashSet(wordDict); dp[0] = true; //初始化 for(int i = 1; i <= n; i++){//背包容量，可以取到n，因为子串获取是左闭右开 for(int j = 0; j <= i; j++ ){//对字典里的子串进行比较//感觉这里可以优化：contains附带了一个O(N)的时间复杂度 if(dp[j] == true && wordDictSet.contains(s.substring(j,i))){ //之前有包括的子串，且后面的位置，也被包括，就赋值为true dp[i] = true; //赋值为true，就可以跳出 break; } } } return dp[n]; } }

【动态规划|115、完全背包-LeetCode-139.单词拆分】