网站源码天堂,怎么做微信网站,企业网站建设新闻发布,建设银行信用卡官网站首页个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主要讲述动态规划算法…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构 http://t.csdnimg.cn/hKh2l 前言这个专栏主要讲述动态规划算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为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, vectorstring wordDict) {int n s.size(); // s的大小vectorbool dp(n1,false); // 表示[0,1]之间是否被字典中的单词连接s s; // 前面加上空格方便计算// 将字典中的单词放入哈希表中(便于查找)unordered_setstring 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];}
};
