网站建设初期推广方式,免费seo推广软件,互联网建站是什么,推广策略组合LeetCode-139. 单词拆分【字典树 记忆化搜索 数组 哈希表 字符串 动态规划】 题目描述#xff1a;解题思路一#xff1a;Python动态规划五部曲#xff1a;定推初遍举【先遍历背包 后遍历物品】必须是排列解题思路二#xff1a;Python动态规划版本二解题思路三#xff1a;回… LeetCode-139. 单词拆分【字典树 记忆化搜索 数组 哈希表 字符串 动态规划】 题目描述解题思路一Python动态规划五部曲定推初遍举【先遍历背包 后遍历物品】必须是排列解题思路二Python动态规划版本二解题思路三回溯 题目描述
给你一个字符串 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 300 1 wordDict.length 1000 1 wordDict[i].length 20 s 和 wordDict[i] 仅由小写英文字母组成 wordDict 中的所有字符串 互不相同
解题思路一Python动态规划五部曲定推初遍举【先遍历背包 后遍历物品】必须是排列
【先遍历物品 后遍历背包】是组合不可用 确定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状态如图
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:dp [False] * (len(s) 1)dp[0] Truefor i in range(1, len(s) 1):for word in wordDict:if i len(word):dp[i] dp[i] or (dp[i-len(word)] and s[i-len(word):i] word)return dp[len(s)]时间复杂度O(n3) 空间复杂度O(n)
解题思路二Python动态规划版本二
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]时间复杂度O(n3) 空间复杂度O(n)
解题思路三回溯
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)时间复杂度O(n3) 空间复杂度O(n2) # 递归
