问题：

给定一个字符串，和一个字典，将字符串切分后，每部分都是字典中字符串，求所有切分可能。

Example 1:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

　　

解法：Backtracking（回溯算法）DFS（深度优先搜索）

简单的回溯，会超时。

• path：到当前位置截止，切分的结果。
• opt：从当前位置，到n个字符所得字符串在字典中，则为符合条件选择。加入path。
• 结束条件：当前位置=s.size。将path加入res。

代码参考：

 1 class Solution {
 2 public:
 3     void backtrack(vector<string>& res, string path, int pos, string s, unordered_set<string>& wordSet) {
 4         if(pos == s.size()) {
 5             path.pop_back();
 6             res.push_back(path);
 7             return;
 8         }
 9         for(int i=pos+1; i<=s.size(); i++) {
10             string tmp = s.substr(pos, i-pos);
11             if(wordSet.count(tmp)!=0) {
12                 backtrack(res, path+tmp+" ", i, s, wordSet);
13             }
14         }
15         return;
16     }
17     vector<string> wordBreak(string s, vector<string>& wordDict) {
18         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
19         vector<string> res;
20         string path;
21         backtrack(res, path, 0, s, wordSet);
22         return res;
23     }
24 };

 

DFS：

递归函数：对每个子字符串，返回要求的所有切分可能。vector<string> res

♻️ 优化方法：在递归中，可能出现重复字符串的求解，因此，使用map，对结果进行保存，每次递归，先check是否已经求解过该字符串s，有的话，之间返回map[s]

1.每次将所求字符串拆分为：尾部字符串endstr，和头部字符串headstr

2.首先，如果尾部字符串=本字符串全部，刚好在字典中，则res+={【endstr】}

3.for 尾部字符串：i～size（i：0～size-1）

        subres = 余下头部字符串 headstr去求递归。

        res += 【每个subres + “ ” + endstr】

4.将当前res存入map，map[s]=res

返回res。

 

代码参考：

 1 class Solution {
 2 public:
 3     vector<string> DFS(string s, unordered_map<string, vector<string>>& m, unordered_set<string>& wordSet) {
 4         if(m.count(s)) return m[s];
 5         vector<string> res;
 6         if(wordSet.count(s)) {
 7             res.push_back(s);
 8         }
 9         for(int i=0; i<s.size(); i++) {
10             string endstr = s.substr(i);
11             if(wordSet.count(endstr)) {
12                 string headstr = s.substr(0, i);
13                 vector<string> subres = DFS(headstr, m, wordSet);
14                 for(string path: subres) {
15                     res.push_back(path+" "+endstr);
16                 }
17             }
18         }
19         m[s] = res;
20         return res;
21     }
22     vector<string> wordBreak(string s, vector<string>& wordDict) {
23         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
24         unordered_map<string, vector<string>> m;
25         vector<string> res;
26         res = DFS(s, m, wordSet);
27         return res;
28     }
29 };