题目描述
给定一个字符串s,分割s使得s的每一个子串都是回文串
返回所有的回文分割结果。(注意:返回结果的顺序需要和输入字符串中的字母顺序一致。)
例如:给定字符串s=“aab”,
返回 [“aa”,“b”],↵ [“a”,“a”,“b”]
深度优先搜索思路
子在川上曰:如果要求输出所有可能的解,往往都是要用深度优先搜索。如果是要求找出最优的解,或者解的数量,往往可以使用动态规划。
记住这句话,超级有用。
那么这道题的话,当然是用深度优先搜索的策略了。
先定义两个全局变量,然后通过深度优先搜索,不断维护这两个vector,最后返回答案即可。
我记得前面有一篇很类似的题,leetcode每日一道(10)字符串切分为单词的所有可能的结果。简直一模一样的,只是上一篇把它看成了递归,这次是看成了dfs。因此这类题是一定要掌握的!关键时候能救命啊伙伴们!
另外还有个,如何判定回文串,c++中有反向迭代器,可以一步到位:
bool ishuiwen(string s){
return s==string(s.rbegin(),s.rend());
代码
class Solution {
public:
// 设置两个全局变量
vector<vector<string>> result;
vector<string> cur;
vector<vector<string>> partition(string s) {
dfs(s);
return result;
}
bool ishuiwen(string s){
return s==string(s.rbegin(),s.rend());
}
void dfs(string s){
if (s==""){
result.push_back(cur);
return;
}
for(int i=1;i<=s.length();i++){
if (ishuiwen(s.substr(0,i))){
cur.push_back(s.substr(0,i));
dfs(s.substr(i,s.length()-i));
cur.pop_back();
}
}
}
};