Leetcode 131.分割回文串 回溯 C++实现

Leetcode 131. 分割回文串

问题：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

算法：

创建二维返回数组 ans ，和临时数组 path 。

进入 dfs 函数，当 i==n 时，证明已经递归到最后一个元素，执行完就可以 return 。从 i 到末尾，如果是回文就加入到 path 数组中，然后进入下一层递归。递归结束后将 path 存入返回数组 ans 中，最后恢复现场准备进入下一次递归。

代码：

class Solution {// 判断是否是回文字符串bool isPalindrome(string& s,int left,int right){while(left < right)if(s[left++] != s[right--]) return false;return true;}
public:vector<vector<string>> partition(string s) {vector<vector<string>> ans;// 返回数组ansvector<string> path;// 临时数组pathint n = s.length();// 字符串s的长度nauto dfs = [&](auto&& dfs,int i){if(i == n){// 结束ans.emplace_back(path);return ;}for(int j = i;j < n;j++){if(isPalindrome(s,i,j)){path.push_back(s.substr(i,j - i + 1));dfs(dfs,j + 1);// 进入下一层递归path.pop_back();// 恢复现场}// 如果不满足回文条件，不能return，要继续向后加字母。例如efe这个字符串，ef 不满足条件，但是向后加字母到 efe 就又满足了}};dfs(dfs,0);// 递归入口return ans;}
};

p.s. string.substr( a , b )    :   从 string 的第 a 个位置开始，连续读取 b 个数量的字符。