r*******n
发帖数: 3020 | 1 vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
//DP
for(int i=0; i
for(int j=i;j
if(dict.find(s.substr(i,j-i+1))!=dict.end()){
table[i][j]=true;
}
}
}
//Backtracking using DFS
function dfs;
dfs=[&](int col, string path){
if(col==n){
result.push_back(path);
return;
}
for(int k=col; k
if(table[col][k]){
dfs(k+1, path+" "+s.substr(col, k-col+1));
}
}
};
dfs(0, "");
return result;
} | b*******e
发帖数: 123 | 2 My approach is very similar to yours. the difference is the meaning of DP
table. My DP table is 1-D bool, it tracks whether there exist a word break
from i to end. When you do DFS, you can skip the index that doesn't have a
solution when going forward. | r*******n
发帖数: 3020 | 3 多谢，改了后过了OJ。
如你所说，我加了1-D bool table来记录有没有解
后面DFS根据这个如果没有解就停止递归搜索
把整个code贴下面
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
vector has_solution(n+1,false);
has_solution[n]=true;
for(int j=n-1; j>=0; --j){
for(int i=j; i>=0; --i){
if(dict.find(s.substr(i,j-i+1))!=dict.end()&&has_solution[j+
1]){
has_solution[i]=true;
}
}
}
//DP
for(int i=0; i
for(int j=i;j
if(dict.find(s.substr(i,j-i+1))!=dict.end()){
table[i][j]=true;
}
}
}
//Backtracking using DFS
function dfs;
dfs=[&](int col, string path){
if(col==n){
result.push_back(path.substr(1));
return;
}
for(int k=col; k
if(table[col][k]&&has_solution[k+1]){
dfs(k+1, path+" "+s.substr(col, k-col+1));
}
}
};
dfs(0, "");
return result;
}
【在 b*******e 的大作中提到】
: My approach is very similar to yours. the difference is the meaning of DP
: table. My DP table is 1-D bool, it tracks whether there exist a word break
: from i to end. When you do DFS, you can skip the index that doesn't have a
: solution when going forward.
|
|
