I
第一问上来以为是简单的考察DFS搜索，果断敲了一发结果TLE。看了一眼Tags提示，原来是个DP问题。状态表示很简单，设dp[i]表示前i个字符是否能够由字典中的单词组成，则很容易由dp[i-1]推出dp[i]。核心思路是，最后第i个字符，可以尝试自己组成一个单词、与第i-1个字符组成单词、与后两个字符组成单词……一直到尝试前i个字符能否组成单独一个字典中的单词。这些尝试中只要有一个成功，就可以标记dp[i]=true。
II
第二问是第一问的进一步加深，要求输出所有可能的组成情况。还是使用递归回溯的思路，首先我们在DP的过程中记录当前状态是由上次的哪个状态转移而来，然后从末状态执行一次DFS，搜索到起始状态，这个过程中就可以找出所有可能的解。由于先前的DP已经进行了预处理，搜索的过程中每次DFS一定都可以抵达终点，也就是说，每次搜索必然是找到一个可行解，因此这个算法的时间复杂度是最低的，恰好找出了所有答案。
代码
class Solution {
public:
static const int MAX = 2000;
int dp[MAX];
vector<int> prev[MAX];
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> ans;
vector<string> result;
for ( int i = 0; i < s.size(); i++ ) prev[i].clear();
dp[0] = dict.find(s.substr(0, 1)) != dict.end();
prev[0].push_back(-1);
for ( int i = 1; i < s.length(); i++ ) {
string str;
str += s[i];
for ( int j = i - 1; j >= -1; j-- ) {
if ( (j == -1 || dp[j]) && dict.find(str) != dict.end() ) {
dp[i] = true;
prev[i].push_back(j);
}
str = s[j] + str;
}
}
if ( dp[s.size() - 1] ) DFS(s.size() - 1, ans, result, s);
return result;
}
void DFS( int pos, vector<string> & ans,vector<string> & result, string & s ) {
if ( pos == -1 ) {
string cur;
for ( int i = ans.size() - 1; i >= 0; i-- ) {
cur += ans[i];
if ( i ) cur += ' ';
}
result.push_back(cur);
return;
}
for ( int i = 0; i < prev[pos].size(); i++ ) {
int len = pos - ( prev[pos][i] + 1 ) + 1;
int start = prev[pos][i] + 1;
ans.push_back(s.substr(start, len));
DFS(prev[pos][i], ans, result, s);
ans.pop_back();
}
}
};