安康网站建设公司电话,重庆百度竞价托管,网站开发参考书,做企业的网站都要准备什么手续139. 单词拆分 确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话#xff0c;dp[i]为true#xff0c;表示可以拆分为一个或多个在字典中出现的单词。 确定递推公式 如果确定dp[j] 是true#xff0c;且 [j, i] 这个区间的子串出现在字典里#xff0c;那么dp[i]一定是tru…139. 单词拆分 确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话dp[i]为true表示可以拆分为一个或多个在字典中出现的单词。 确定递推公式 如果确定dp[j] 是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是true。j i 。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。
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只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。
确定遍历顺序 题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。
还要讨论两层for循环的前后顺序。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
/*** param {string} s* param {string[]} wordDict* return {boolean}*/
var wordBreak function (s, wordDict) {let dp Array(s.length 1).fill(false);dp[0] true;for (let i 0; i s.length; i) {for (let j 0; j wordDict.length; j) {if (i wordDict[j].length) {if (s.slice(i - wordDict[j].length, i) wordDict[j] dp[i - wordDict[j].length]) {dp[i] true}}}}return dp[s.length];
};
