题目：
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
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"].
思路：
还是DFS，但是由于字符串中可能存在相同的子串，所以我们在DFS搜索的过程中还需要记忆已经找到的结果，这样可以大大提高效率（否则过不了大数据）。在DFS的搜索过程中，我们首先判断其前i个字符所构成的子字符串是否存在于字典中，如果是，再递归地搜索从i之后的子串所能构成的结果数组；递归完成之后的关键一步就是合成结果，也就是将前i个字符所构成的子字符串和递归返回的结果合并起来，作为最终结果。当然在返回之前不能忘记把它放在哈希列表中。
代码：
class Solution { public: vector<string> wordBreak(string s, unordered_set<string>& wordDict) { return dfs(s, wordDict); } private: vector<string> dfs(string s, unordered_set<string>& wordDict) { if(hash.count(s) > 0) { return hash[s]; } vector<string> ret; if(wordDict.count(s) > 0) { ret.push_back(s); } for(int i = 1; i < s.length(); ++i) { string first = s.substr(0, i); if(wordDict.count(first) > 0) { vector<string> ans = dfs(s.substr(i), wordDict); for(auto val : ans) { ret.push_back(first + " " + val); } } } hash[s] = ret; return ret; } unordered_map<string, vector<string>> hash; };