网站建设设计问卷,非常旺财的公司名字,唐山高端品牌网站建设,温州品牌网站建设139.单词拆分 力扣题目链接(opens new window)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明#xff1a;
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
…139.单词拆分 力扣题目链接(opens new window)
给定一个非空字符串 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 #算法公开课 《代码随想录》算法视频公开课 (opens new window)你的背包如何装满| LeetCode139.单词拆分 (opens new window)相信结合视频再看本篇题解更有助于大家对本题的理解。
#思路 看到这道题目的时候大家应该回想起我们之前讲解回溯法专题的时候讲过的一道题目回溯算法分割回文串 (opens new window)就是枚举字符串的所有分割情况。
回溯算法分割回文串 (opens new window)是枚举分割后的所有子串判断是否回文。
本道是枚举分割所有字符串判断是否在字典里出现过。
那么这里我也给出回溯法C代码
class Solution {
private:bool backtracking (const string s, const unordered_setstring wordSet, int startIndex) {if (startIndex s.size()) {return true;}for (int i startIndex; i s.size(); i) {string word s.substr(startIndex, i - startIndex 1);if (wordSet.find(word) ! wordSet.end() backtracking(s, wordSet, i 1)) {return true;}}return false;}
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());return backtracking(s, wordSet, 0);}
};这个时间复杂度其实也是O(2^n)。只不过对于上面那个超时测试用例优化效果特别明显。
这个代码就可以AC了当然回溯算法不是本题的主菜背包才是
#背包问题 单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词说明就是一个完全背包
动规五部曲分析如下
确定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循环遍历物品。
我在这里做一个总结
求组合数动态规划518.零钱兑换II (opens new window)求排列数动态规划377. 组合总和 Ⅳ (opens new window)、动态规划70. 爬楼梯进阶版完全背包 (opens new window)求最小数动态规划322. 零钱兑换 (opens new window)、动态规划279.完全平方数(opens new window)
而本题其实我们求的是排列数为什么呢。 拿 s “applepenapple”, wordDict [“apple”, “pen”] 举例。
“apple”, “pen” 是物品那么我们要求 物品的组合一定是 “apple” “pen” “apple” 才能组成 “applepenapple”。
“apple” “apple” “pen” 或者 “pen” “apple” “apple” 是不可以的那么我们就是强调物品之间顺序。
所以说本题一定是 先遍历 背包再遍历物品。
举例推导dp[i] 以输入: s “leetcode”, wordDict [“leet”, “code”]为例dp状态如图 dp[s.size()]就是最终结果。
动规五部曲分析完毕C代码如下
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true;for (int i 1; i s.size(); i) { // 遍历背包for (int j 0; j i; j) { // 遍历物品string word s.substr(j, i - j); //substr(起始位置截取的个数)if (wordSet.find(word) ! wordSet.end() dp[j]) {dp[i] true;}}}return dp[s.size()];}
};时间复杂度O(n^3)因为substr返回子串的副本是O(n)的复杂度这里的n是substring的长度 空间复杂度O(n)
拓展
关于遍历顺序再给大家讲一下为什么 先遍历物品再遍历背包不行。
这里可以给出先遍历物品再遍历背包的代码
class Solution { public: bool wordBreak(string s, vector wordDict) { unordered_set wordSet(wordDict.begin(), wordDict.end()); vector dp(s.size() 1, false); dp[0] true; for (int j 0; j wordDict.size(); j) { // 物品 for (int i wordDict[j].size(); i s.size(); i) { // 背包 string word s.substr(i - wordDict[j].size(), wordDict[j].size()); // cout word endl; if ( word wordDict[j] dp[i - wordDict[j].size()]) { dp[i] true; } // for (int k 0; k s.size(); k) cout dp[k] ; //这里打印 dp数组的情况 // cout endl; } } return dp[s.size()];
}}; 使用用例s “applepenapple”, wordDict [“apple”, “pen”]对应的dp数组状态如下 最后dp[s.size()] 0 即 dp[13] 0 而不是1因为先用 “apple” 去遍历的时候dp[8]并没有被赋值为1 还没用pen所以 dp[13]也不能变成1。
除非是先用 “apple” 遍历一遍再用 “pen” 遍历此时 dp[8]已经是1最后再用 “apple” 去遍历dp[13]才能是1。
如果大家对这里不理解建议可以把我上面给的代码拿去力扣上跑一跑把dp数组打印出来对着递推公式一步一步去看思路就清晰了。
Python 回溯
class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) - bool:# 边界情况已经遍历到字符串末尾返回Trueif startIndex len(s):return True# 遍历所有可能的拆分位置for i in range(startIndex, len(s)):word s[startIndex:i 1] # 截取子串if word in wordSet and self.backtracking(s, wordSet, i 1):# 如果截取的子串在字典中并且后续部分也可以被拆分成单词返回Truereturn True# 无法进行有效拆分返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict) # 转换为哈希集合提高查找效率return self.backtracking(s, wordSet, 0)DP版本一
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict)n len(s)dp [False] * (n 1) # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词dp[0] True # 初始状态空字符串可以被拆分成单词for i in range(1, n 1): # 遍历背包for j in range(i): # 遍历单词if dp[j] and s[j:i] in wordSet:dp[i] True # 如果 s[0:j] 可以被拆分成单词并且 s[j:i] 在单词集合中存在则 s[0:i] 可以被拆分成单词breakreturn dp[n]DP版本二
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False]*(len(s) 1)dp[0] True# 遍历背包for j in range(1, len(s) 1):# 遍历单词for word in wordDict:if j len(word):dp[j] dp[j] or (dp[j - len(word)] and word s[j - len(word):j])return dp[len(s)]
