LeetCode刷题--- 单词拆分
个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归题
【C++】
http://t.csdnimg.cn/6AbpV
数据结构
前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分：
1、题目解析
2、算法原理思路讲解
3、代码实现
单词拆分
题目链接：单词拆分
题目
给你一个字符串 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中的所有字符串 互不相同
解法
算法原理解析
我们这题使用动态规划，我们做这类题目可以分为以下五个步骤
- 状态显示
- 状态转移方程
- 初始化（防止填表时不越界）
- 填表顺序
- 返回值
- 状态显示
dp[i] 表示
：
[0, i]
区间内的字符串，能否被字典中的单词拼接而成。
- 状态转移方程
对于
dp[i]
，为了确定当前的字符串能否由字典里面的单词构成，根据最后⼀个单词的起始位 置 j
，我们可以将其分解为前后两部分：
- 前⾯⼀部分 [0, j - 1] 区间的字符串；
- 后⾯⼀部分 [j, i] 区间的字符串。
其中前⾯部分我们可以在
dp[j - 1]
中找到答案，后⾯部分的子串可以在字典里面找到。 因此，我们得出⼀个结论：当我们在从 0 ~ i
枚举
j
的时候，只要
dp[j - 1] = true 并且后⾯部分的子串s.substr(j, i - j + 1)
能够在字典中找到，那么
dp[i] = true 。
- 初始化（防止填表时不越界）
- 在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = true ，可以理解为空串能够拼接⽽成。
- 其中为了⽅便处理下标的映射关系，我们可以将字符串前⾯加上⼀个占位符 s = ' ' + s ，这 样就没有下标的映射关系的问题了，同时还能处理「空串」的情况。
- 填表顺序
根据「状态转移⽅程」易得，填表顺序为「从左往右」。
- 返回值
由「状态表⽰」可得：返回
dp[n]
位置的布尔值。
代码实现
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
int n = s.size();// s的大小
vector<bool> dp(n+1,false);// 表示[0,1]之间，是否被字典中的单词连接
s = ' ' + s;// 前面加上空格，方便计算
// 将字典中的单词放入哈希表中(便于查找)
unordered_set<string> hash;
for (auto& e : wordDict)
{
hash.insert(e);
}
// 初始化
dp[0] = true;
// 填表
for (int i = 1; i <= n; i++)
{
for (int j = i; j >= 1; j--)
{
if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
{
dp[i] = true;
break;
}
}
}
return dp[n];
}
};原文地址：https://blog.csdn.net/weixin_74268082/article/details/136559417
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！