爱站网自媒体数据,做游戏网站用什么软件,做网站的哪里好,wordpress判断子分类题目链接#xff1a;139. 单词拆分
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例…题目链接139. 单词拆分
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以由 leet 和 code 拼接成。示例 2
输入: s applepenapple, wordDict [apple, pen]
输出: true
解释: 返回 true 因为 applepenapple 可以由 apple pen apple 拼接成。注意你可以重复使用字典中的单词。示例 3
输入: s catsandog, wordDict [cats, dog, sand, and, cat]
输出: false提示
1 s.length 3001 wordDict.length 10001 wordDict[i].length 20s 和 wordDict[i] 仅由小写英文字母组成wordDict 中的所有字符串 互不相同
文章讲解代码随想录
视频讲解动态规划之完全背包你的背包如何装满| LeetCode139.单词拆分_哔哩哔哩_bilibili
题解1动态规划
思路这是一个完全背包问题字符串的长度为背包容量字典为物品求解物品的排列能否装满背包。
动态规划分析
dp 数组以及下标的含义dp[j] 代表从 s 的头部截取长度为 j 的字符串能否由字典组成。递推公式dp[j - wordDict[i].length] 为 true 时dp[j] dp[j - wordDict[i].length]。dp 数组初始化dp[0] 初始化为 true为了保证取最小的结果正确后续元素需初始化为 false。遍历顺序本题求排列应先遍历背包再遍历物品。打印 dp 数组以输入 s leetcode、wordDict [leet,code] 为例dp 数组为 [ true, false, false, false, true, false, false, false, true ]。
/*** param {string} s* param {string[]} wordDict* return {boolean}*/
var wordBreak function(s, wordDict) {const dp new Array(s.length 1).fill(false);dp[0] true;for (let j 0; j s.length; j) {for (let i 0; i wordDict.length; i) {if (j wordDict[i].length s.substring(0, j).endsWith(wordDict[i]) dp[j - wordDict[i].length]) {dp[j] true;}}}return dp[s.length];
};
分析令 n 为 wordDict 的长度m 为 s 的长度则时间复杂度为 O(n * m²)空间复杂度为 O(m)。
题解2回溯法
思路使用回溯法求解分割问题使用记忆化递归优化速度。
/*** param {string} s* param {string[]} wordDict* return {boolean}*/
var wordBreak function(s, wordDict) {const set new Set(wordDict);const memory []; // 保存每次计算的以 start 起始的计算结果const backtracking function (start) {if (start s.length) {return true;}// 如果 memory[start] 不是未定义了直接使用 memory[start] 作为结果if (memory[start] ! undefined) {return memory[start];}for (let i start; i s.length; i) {if (set.has(s.substring(start, i 1)) backtracking(i 1)) {return true;}}memory[start] false; // 记录以 startIndex 开始的子串是不可被拆分的return false;}return backtracking(0);
};
分析时间复杂度为 O(2 ^ n)空间复杂度为 O(n)。
收获
练习完全背包问题的求解理解不同遍历顺序的区别。
