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

糖逗

题目描述：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <string>
#include <vector>
#include <iostream>

using namespace std;



bool valid(string s){
        return s == string(s.rbegin(), s.rend());
}

void dfs(vector<vector<string> > & res, string s, vector<string> & temp){
        
        if(s == ""){
                res.push_back(temp);
                return;
        }
        for(int i = 0; i < s.size(); i++){
                string sub = s.substr(0, i+1);
                if(valid(sub)){
                        temp.push_back(sub);
                        dfs(res, s.substr(i+1, s.size() - 1-i), temp);
                        temp.pop_back();
                        
                }
         }
        
        
}

vector<vector<string> > solution(string s) {
    vector<vector<string> > res;
    vector<string> temp;
    dfs(res, s, temp);
    return res;
}



int main(void){
        string input;
        cin >> input;
        vector<vector<string> > res  = solution(input); 
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[0].size(); j++){
                        cout << res[i][j] << " "; 
                }
                cout << endl;
        } 

        return 0;
}