大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
题解
记忆化搜索+hash
class Solution {
public:
string t;
unordered_map<string,bool>mm;
int Min,Max;
vector<string> rem[10000];
int max(int a,int b){
return a > b ? a : b;
}
int min(int a,int b){
return a < b ? a : b;
}
void dfs(int u,string &s){
if(rem[u].size() != 0)return;
if(u == s.size()){
rem[u].push_back("");
return;
}
for(int len = Min;len <= Max;len ++){
if(s.size() - u >= len && mm.find(s.substr(u,len)) != mm.end()){
dfs(u + len,s);
for(auto &line : rem[u + len]){
rem[u].push_back(s.substr(u,len) + " " + line);
}
}
}
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
t = "";
Min = 0x3f3f3f3f,Max = 0;
for(int i = 0;i < wordDict.size();i ++){
Min = min(wordDict[i].size(),Min);
Max = max(wordDict[i].size(),Max);
}
for(auto &s : wordDict){
mm[s] = true;
}
dfs(0,s);
for(auto & s : rem[0]){
s.erase(s.size() - 1,1);
}
return rem[0];
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168641.html原文链接：https://javaforall.net
