Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog",
"cat sand dog"].
算法思想：
用dp[i][j]保存從i到j是否在字典中存在，然後根據dp遞歸將字符串構造出來
思想比較簡單，但是需要注意一點：如果從前至後遞歸構造字符串，比如我第一次寫的遞歸代碼
void dfs(int k, string &s){
if(k==length){
string str;
for(int i=0;i
提交上去最後一條測試數據總是超時，所以我們得從後向前遞歸，減少遞歸次數
void dfs(int k, string &s){
if(k==-1){
string str;
for(int i=t.size()-1;i>=0;i--){
str += t[i];
if(i!=0)
str.push_back(' ');
}
result.push_back(str);
return;
}
for(int i=0;i<=k;i++){
if(dp[i][k-i]){
t.push_back(s.substr(i,k-i+1));
dfs(i-1,s);
t.pop_back();
}
}
}AC的代碼如下：
class Solution{
public:
vector result;
vector> dp;
vector t;
int length;
void dfs(int k, string &s){
if(k==-1){
string str;
for(int i=t.size()-1;i>=0;i--){
str += t[i];
if(i!=0)
str.push_back(' ');
}
result.push_back(str);
return;
}
for(int i=0;i<=k;i++){
if(dp[i][k-i]){
t.push_back(s.substr(i,k-i+1));
dfs(i-1,s);
t.pop_back();
}
}
}
vector wordBreak(string s, unordered_set &dict) {
length=s.size();
dp.resize(length);
for(int i=0;i
