东光网站制作,网站开发任职要求,报纸做垂直门户网站,企业培训视频跳转汇总链接
#x1f449;#x1f517;算法题汇总链接 1.4 单词拆分
#x1f517;题目链接 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且…
跳转汇总链接
算法题汇总链接 1.4 单词拆分
题目链接 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 状态表示 本题依旧以 s 字符串上 i 位置为结尾作为一个状态。这个状态还能分成两部分将最后一部分的开头设做 j 位置[0, j) 能被字典中的词拼出来 [j, i] 是在字典中的词以这样分析如果有一种情况下这两部分都是满足的这个 i 位置就可以设成 true 了。dp[i] 表示以 i 位置为结尾的字符串能否被字典中的单词拼出来。 状态转移方程 这里的位置划分明显有两个变量 i 和 j 有 0 j i分析 i 位置的状态转移方程 dp[i] if (dp[j] true s.substr(j, i-j) 在 wordDict 中), trueelse, false初始化 表头添加一个元素初始化为 true对 s 字符串也添加一个占位符在前面便于访问原始数据 填表顺序 从左往右依次填写 返回值 dp 表的末尾值 代码如下 下面还有优化版本
class Solution {
public:bool IsInDict(const string str, const vectorstring wordDict){for(auto e : wordDict){if (str e){return true;}}return false;}bool wordBreak(string s, vectorstring wordDict) {int n s.size();vectorint dp(n 1);dp[0] 1;s x s;for(int i 1; i n 1; i){for(int j 1; j i; j){if(dp[j-1] 1 IsInDict(s.substr(j, i-j1), wordDict)){dp[i] 1;break;}}}return dp[n];}
};… … 这里 IsInDict 的实现是不是有点傻字典查询属于“在不在”问题用 hash 怎么样~
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring hash;for(auto e : wordDict) hash.insert(e);int n s.size();vectorbool dp(n 1); // bool在vector中默认值是0跟int一样啦dp[0] true; // 保证后续结果正确s x s; // 保持统一方便读取原数据for(int i 1; i n 1; i){for(int j 1; j i; j){if(dp[j-1] 1 hash.count((s.substr(j, i-j1)))){dp[i] true;break;}}}return dp[n];}
};如果本文对你有些帮助欢迎 点赞 收藏 关注你的支持是对作者大大莫大的鼓励(✿◡‿◡) 若有差错恳请留言指正~~
