Word Break II
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