光效网站,南宁建设集团招聘信息网站,做网站做本地服务器吗,微官网建设公司排行文章目录 Day46单词拆分题目思路代码 Day46
单词拆分
139. 单词拆分 - 力扣#xff08;LeetCode#xff09;
题目
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明#xff1a;
拆… 文章目录 Day46单词拆分题目思路代码 Day46
单词拆分
139. 单词拆分 - 力扣LeetCode
题目
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 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
思路
动规五部曲
确定dp数组以及下标的含义
dp[j]:长度为 j 的字符串dp[j] 为true表示可以拆分为一个或者多个在字典出现过的单词
确定递推公式
字符串(子串)长度为 i
如果确定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]初始为true完全就是为了推导公式。
遍历顺序
题目中说是拆分为一个或多个在字典中出现的单词所以这是完全背包。
还要讨论两层for循环的前后顺序。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
本题其实我们求的是排列数因为有要求物品之间顺序。
举例推导dp[i]
以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g1c4AFJC-1690703105690)(https://code-thinking-1253855093.file.myqcloud.com/pics/20210202162652727.jpg “139.单词拆分”)]
代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean dp[] new boolean[s.length() 1];dp[0] true;SetString set new HashSet(wordDict);for(int i 1; i s.length(); i){for(int j 0; j i; j){String str s.substring(j, i);if(set.contains(str) dp[j]){dp[i] true;break;}}}return dp[s.length()];}
}// 另一种思路的背包算法
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i s.length(); i) {for (String word : wordDict) {int len word.length();if (i len dp[i - len] word.equals(s.substring(i - len, i))) {dp[i] true;break;}}}return dp[s.length()];}
}
