NC182. 单词拆分(二)
描述
示例1
输入:
"nowcoder",["now","coder","no","wcoder"]
输出:
["no wcoder","now coder"]
示例2
输入:
"nowcoder",["now","wcoder"]
输出:
[]
示例3
输入:
"nowcoder",["nowcoder"]
输出:
["nowcoder"]
示例4
输入:
"nownowcoder",["now","coder"]
输出:
["now now coder"]
说明:
你可以重复使用 dic 数组中的字符串C++ 解法, 执行用时: 3ms, 内存消耗: 768KB, 提交时间: 2022-02-03
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串vector
* @return string字符串vector
*/
bool cmp(pair<int,int> &a, pair<int,int> &b)
{
if(a.first < b.first)
return true;
else if(a.first == b.first)
{
if(a.second < b.second)
return true;
else
return false;
}
else
return false;
}
vector<string> wordDiv(string s, vector<string>& dic)
{
vector<string> ret;
int maxWidth = 0;
unordered_set<string> wordDictSet;
vector<pair<int,int>> range;
for (int i=0; i<dic.size(); ++i)
{
wordDictSet.insert(dic[i]);
if(dic[i].length() > maxWidth)
maxWidth = dic[i].length();
}
//定义dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1]
//是否能被空格拆分成若干个字典中出现的单词
vector<bool> dp(s.size()+1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i)
for (int j = max(i - maxWidth, 0); j <=i ; ++j)
{
if (dp[j] &&
wordDictSet.find(s.substr(j, i-j)) != wordDictSet.end())
{
dp[i] = true;
pair<int, int> loc(j, j + i-j-1);
range.push_back(loc);
//break;
}
}
if(dp[s.size()] == false) return ret;
sort(range.begin(), range.end());
vector<bool> isVisited(range.size(), false);
for(int i=0; i<range.size(); ++i)
{
if(range[i].first == 0)
{
isVisited[i] = true;
vector<string> ans;
ans.push_back(s.substr(range[i].first, range[i].second - range[i].first + 1));
dfs(range, i, s, ans, isVisited,ret);
}
}
sort(ret.begin(), ret.end());
return ret;
}
void dfs(vector<pair<int, int>> &range, int preIdx, string &s, vector<string> &ans, vector<bool> &isVisited, vector<string> &ret)
{
if(range[preIdx].second == s.size()-1)
{
string temp="";
for(int j =0; j<ans.size()-1; ++j)
temp += ans[j] + " ";
temp += ans[ans.size()-1];
ret.push_back(temp);
return;
}
for(int i=preIdx+1; i<range.size(); ++i)
{
if(range[i].first == 1 + range[preIdx].second)
{
isVisited[i] = true;
ans.push_back(s.substr(range[i].first, range[i].second-range[i].first + 1));
dfs(range, i, s, ans, isVisited, ret);
isVisited[i] = false;
ans.pop_back();
}
else if(range[i].first > 1 + range[preIdx].second)
break;
}
}
};
class Solution4 {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串vector
* @return string字符串vector
*/
bool cmp(pair<int,int> &a, pair<int,int> &b)
{
if(a.first < b.first)
return true;
else if(a.first == b.first)
{
if(a.second < b.second)
return true;
else
return false;
}
else
return false;
}
vector<string> wordDiv(string s, vector<string>& dic)
{
vector<string> ret;
int maxWidth = 0;
unordered_set<string> wordDictSet;
vector<pair<int,int>> range;
for (int i=0; i<dic.size(); ++i)
{
wordDictSet.insert(dic[i]);
if(dic[i].length() > maxWidth)
maxWidth = dic[i].length();
}
//定义dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1]
//是否能被空格拆分成若干个字典中出现的单词
vector<bool> dp(s.size()+1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i)
for (int j = max(i - maxWidth, 0); j <=i ; ++j)
{
if (dp[j] &&
wordDictSet.find(s.substr(j, i-j)) != wordDictSet.end())
{
dp[i] = true;
pair<int, int> loc(j, j + i-j-1);
range.push_back(loc);
//break;
}
}
if(dp[s.size()] == false) return ret;
sort(range.begin(), range.end());
vector<bool> isVisited(range.size(), false);
for(int i=0; i<range.size(); ++i)
{
if(range[i].first != 0) break;
int preIdx = i;
string first_str= s.substr(range[i].first, range[i].second - range[i].first + 1);
string nxt_str= "";
for(int j = i+1; j < range.size() && range[preIdx].second != s.size() - 1; ++j)
{
if(range[j].first == range[preIdx].second + 1)
{
preIdx = j;
if(range[j].second != s.size()-1)
nxt_str += s.substr(range[j].first, range[j].second - range[j].first + 1) + " ";
else
break;
}
}
if(preIdx != i)
{
nxt_str += s.substr(range[preIdx].first, range[preIdx].second - range[preIdx].first + 1);
first_str += " " + nxt_str;
}
ret.push_back(first_str);
}
sort(ret.begin(), ret.end());
return ret;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1032KB, 提交时间: 2021-11-25
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串vector
* @return string字符串vector
*/
vector<string> wordDiv(string s, vector<string>& dic) {
int size=s.size();
poslst.resize(size);
int dicsize=dic.size();
unordered_set<string> repeatchk;
for(int i=0;i<dicsize;++i) {
if(repeatchk.count(dic[i])==0) {
repeatchk.insert(dic[i]);
kmp(dic[i], s);
}
}
for(int i=0;i<poslst.size();++i) {
vector<int> &pos=poslst[i];
sort(pos.begin(), pos.end());
}
cat(0, size);
int lstsize=answerlst.size();
vector<string> result(lstsize);
for(int i=0;i<lstsize;++i) {
string &str=result[i];
vector<int> &ans=answerlst[i];
int anssize=ans.size();
str.reserve(size+anssize+1);
str=s.substr(0, ans[0]);
for(int j=1;j<anssize;++j) {
str.push_back(' ');
str.append(s.substr(ans[j-1], ans[j]-ans[j-1]));
}
}
return result;
}
private:
vector<vector<int>> poslst;
vector<vector<int>> answerlst;
vector<int> answer;
void cat(int start, int size) {
if(start==size) {
answerlst.push_back(answer);
return;
}
vector<int> &lst=poslst[start];
for(int i=0;i<lst.size();++i) {
answer.push_back(lst[i]);
cat(lst[i], size);
answer.pop_back();
}
}
void kmp(string S, string T) {
int Ssize=S.size();
int Tsize=T.size();
vector<int> next(Ssize+1, 0);
genNext(S, next);
int i=0;
int j=0;
while(i<Tsize) {
if(j==-1 || S[j]==T[i]) {
++i;
++j;
}
else {
j=next[j];
}
if(j==Ssize) {
j=next[j];
poslst[i-Ssize].push_back(i);
}
}
}
void genNext(string &s, vector<int> &next) {
int size=s.size();
next[0]=-1;
int i=0;
int k=-1;
while(i<size) {
if(k==-1 || s[i]==s[k]) {
++i;
++k;
next[i]=(s[i]==s[k] ? next[k] : k);
}
else {
k=next[k];
}
}
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1048KB, 提交时间: 2022-02-04
class Solution {
public:
unordered_map<string,int> mp;
int len;
vector<string> res;
vector<string> wordDiv(string s, vector<string>& dic) {
int n=dic.size();
len=s.size();
for(int i=0;i<n;i++){
mp[dic[i]]=1;
}
dfs(s,0,"");
return res;
}
void dfs(string s,int st,string str){
if(len==st){
res.push_back(str.substr(0,str.size()-1));
return;
}
string x="";
for(int i=st;i<len;i++){
x+=s[i];
if(mp.count(x)){
dfs(s,i+1,str+x+" ");
}
}
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1060KB, 提交时间: 2022-01-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串vector
* @return string字符串vector
*/
struct treeNode {
string word;
vector<treeNode*> next;
};
vector<string >res;
// 写的太慢 隐藏的题意 可以重复使用字符串
void sub(string s, int idx, string cur, treeNode* root){
if (idx == s.size()) res.push_back(cur);
treeNode* curRoot = root;
for(int i = idx; i < s.size(); i++){
if (i < s.size() && curRoot->next[s[i]-'a'] != NULL) {
curRoot = curRoot->next[s[i]-'a'];
}else return ;
if (curRoot->word != ""){
string next = cur + " " + curRoot->word;
if (cur == "") next = curRoot->word;
sub(s, i+1, next, root);
}
}
return;
}
vector<string> wordDiv(string s, vector<string>& dic) {
// write code here
// dict用字典树重新
treeNode* root = new treeNode();
root->next.resize(26);
for(int i = 0; i < dic.size(); i++){
string cur = dic[i];
treeNode* temp = root;
for(int j = 0; j < cur.size(); j++){
if (temp->next[cur[j]-'a'] == NULL){
treeNode* c = new treeNode();
c->next.resize(26);
temp->next[cur[j]-'a'] = c;
}
temp = temp->next[cur[j] - 'a'];
}
temp->word = cur;
}
string buf = "";
sub(s, 0, buf, root);
//sort(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 1064KB, 提交时间: 2022-02-10
class Solution {
public:
vector<string> str_vec;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串vector
* @return string字符串vector
*/
vector<string> wordDiv(string s, vector<string>& dic) {
// write code here
int len_s = s.length();
assert(len_s && len_s<=20);
str_vec = vector<string>();
unordered_map<char, unordered_set<string>> ch_str_unset_unmap;
for(string &str : dic){
assert(!str.empty() && str.length()<=20);
ch_str_unset_unmap[ str[0] ].insert(str);
}
if( !ch_str_unset_unmap.count( s[0] ) ) return {};
for(const string &str : ch_str_unset_unmap[ s[0] ]){
int len_str = str.length();
if(len_str > len_s) continue;
int idx = 0;
while(idx<len_str && str[idx]==s[idx])
++idx;
if(idx == len_str) DFS(ch_str_unset_unmap, s, len_s, len_str, str);
}
sort(str_vec.begin(), str_vec.end());
return str_vec;
}
void DFS(unordered_map<char, unordered_set<string>> &ch_str_unset_unmap,
string &s, const int len_s, int next_idx, string cur_str)
{
if(next_idx < len_s){
for(const string &str : ch_str_unset_unmap[ s[next_idx] ]){
int len_str = str.length();
if(next_idx+len_str > len_s) continue;
int idx = 0;
while(idx<len_str && str[idx]==s[ next_idx+idx ])
++idx;
if(idx == len_str) DFS(ch_str_unset_unmap, s, len_s, next_idx+len_str, cur_str+' '+str);
}
}
else str_vec.push_back(cur_str);
}
};