C++刷leetcode（131. 分割回文串）【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:38 编辑题目描述：
给定一个字符串 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.size(); j++){
cout << res << " ";
}
cout << endl;
}
return 0;
}
页:
[1]