怎么样可以做网站充值代理,互动 网站建设,设计师装修网,全网影视vip网站建设139. 单词拆分 难度#xff1a;中等 力扣地址#xff1a;https://leetcode.cn/problems/word-break/description/ 问题描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意#xff1a;不要求字…139. 单词拆分 难度中等 力扣地址https://leetcode.cn/problems/word-break/description/ 问题描述
给你一个字符串 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 中的所有字符串 互不相同
问题分析
套公式完全背包之前需要先回顾一下完全背包问题并结合本道题内容进行适配。 接着我们回顾一下完全背包问题的求解过程这个非常基础也非常重要。 理解完全背包问题以后接下来就是真的套公式了最关键的地方还是在于如何定义状态转移方程这个过程也比较难需要理解题目的意思并且清楚状态转移的条件。
解题代码
分析在前面已经进行介绍这里我们逐行解释代码的作用如果有任何疑问欢迎后面留言。
C 解题代码
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {// 将字典中的单词存储到 unordered_set 中以加快查找速度unordered_setstring wordSet(wordDict.begin(), wordDict.end());// 动态规划数组 dp其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词vectorbool dp(s.size() 1, false);// 初始化空字符串总是可以被拆分的dp[0] true; // 遍历字符串 s 的每一个字符位置 ifor (int i 1; i s.size(); i) {// 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for (int j 0; j i; j) {string target s.substr(j, i - j);// 如果 dp[j] 为 true且目标子串在字典中if (dp[j] wordSet.find(target) ! wordSet.end()) {// 则将 dp[i] 设为 true表示前 i 个字符可以被拆分dp[i] true;// 找到一个合法的拆分跳出内层循环break;}}}// 返回 dp[s.size()]表示整个字符串 s 是否可以被拆分成字典中的单词return dp[s.size()];}
};对应的 Java 版本为
class Solution {public boolean wordBreak(String s, ListString wordDict) {// 将字典中的单词存储到 HashSet 中以加快查找速度SetString wordSet new HashSet(wordDict);// 动态规划数组 dp其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词boolean[] dp new boolean[s.length() 1];// 初始化空字符串总是可以被拆分的dp[0] true;// 遍历字符串 s 的每一个字符位置 ifor (int i 1; i s.length(); i) {// 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for (int j 0; j i; j) {String target s.substring(j, i);// 如果 dp[j] 为 true且目标子串在字典中if (dp[j] wordSet.contains(target)) {// 则将 dp[i] 设为 true表示前 i 个字符可以被拆分dp[i] true;// 找到一个合法的拆分跳出内层循环break;}}}// 返回 dp[s.length()]表示整个字符串 s 是否可以被拆分成字典中的单词return dp[s.length()];}
}对应的python版本代码为
class Solution:def wordBreak(self, s: str, wordDict: list[str]) - bool:# 将字典中的单词存储到 set 中以加快查找速度wordSet set(wordDict)# 动态规划数组 dp其中 dp[i] 表示 s 的前 i 个字符是否可以被拆分成字典中的单词dp [False] * (len(s) 1)# 初始化空字符串总是可以被拆分的dp[0] True# 遍历字符串 s 的每一个字符位置 ifor i in range(1, len(s) 1):# 检查从 j 到 i 的子字符串 s[j:i] 是否在字典中for j in range(i):target s[j:i]# 如果 dp[j] 为 True且目标子串在字典中if dp[j] and target in wordSet:# 则将 dp[i] 设为 True表示前 i 个字符可以被拆分dp[i] True# 找到一个合法的拆分跳出内层循环break# 返回 dp[len(s)]表示整个字符串 s 是否可以被拆分成字典中的单词return dp[len(s)]总结
本次例子中我们不再通过若干个例子介绍拆分过程主要强调如何套公式但是这些都是建立在对原版的完全背包问题熟悉的基础上如果对完全背包问题不太熟悉建议参考本博客中介绍的完全背包问题 4 步解题法接着再套到这个题中理解。 Smileyan 2024.06.30 20:37
