大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 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
- 记忆化搜索
class Solution {
public:
set<string>m;
bool wordBreak(string s, vector<string>& wordDict) {
if(s == "")return true;
if(m.find(s) != m.end())return false;
for(auto &a : wordDict){
int len = a.size();
if(s.size() >= len){
string t = s.substr(0,len);
if(t == a && wordBreak(s.substr(len),wordDict))return true;
}
}
m.insert(s);
return false;
}
};
- 动态规划
const int N = 1e5 + 10;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
bool f[N] = {
false};
f[0] = true;
for(int i = 1;i <= n;i ++){
for(auto &w : wordDict){
int l = i - w.size();
int len = w.size();
if(l >= 0 && w == s.substr(l,len)){
f[i] = f[i] | f[l];
}
}
}
return f[n];
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168555.html原文链接：https://javaforall.net
