C++刷leetcode（131. 分割回文串）【深度优先搜索】

糖逗

题目描述：

1. 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
   
2. 
   
3. 返回 s 所有可能的分割方案。
   
4. 
   
5. 示例:
   
6. 
   
7. 输入: "aab"
   
8. 输出:
   
9. [
   
10.   ["aa","b"],
    
11.   ["a","a","b"]
    
12. ]
    
13. 
    
14. 来源：力扣（LeetCode）
    
15. 链接：https://leetcode-cn.com/problems/palindrome-partitioning
    
16. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <string>
   
2. #include <vector>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. 
   
8. 
   
9. bool valid(string s){
   
10.         return s == string(s.rbegin(), s.rend());
    
11. }
    
12. 
    
13. void dfs(vector<vector<string> > & res, string s, vector<string> & temp){
    
14.        
    
15.         if(s == ""){
    
16.                 res.push_back(temp);
    
17.                 return;
    
18.         }
    
19.         for(int i = 0; i < s.size(); i++){
    
20.                 string sub = s.substr(0, i+1);
    
21.                 if(valid(sub)){
    
22.                         temp.push_back(sub);
    
23.                         dfs(res, s.substr(i+1, s.size() - 1-i), temp);
    
24.                         temp.pop_back();
    
25.                        
    
26.                 }
    
27.         }
    
28.        
    
29.        
    
30. }
    
31. 
    
32. vector<vector<string> > solution(string s) {
    
33.     vector<vector<string> > res;
    
34.     vector<string> temp;
    
35.     dfs(res, s, temp);
    
36.     return res;
    
37. }
    
38. 
    
39. 
    
40. 
    
41. int main(void){
    
42.         string input;
    
43.         cin >> input;
    
44.         vector<vector<string> > res  = solution(input);
    
45.         for(int i = 0; i < res.size(); i++){
    
46.                 for(int j = 0; j < res[0].size(); j++){
    
47.                         cout << res[i][j] << " ";
    
48.                 }
    
49.                 cout << endl;
    
50.         }
    
51. 
    
52.         return 0;
    
53. }

复制代码