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;// 返回数组ans
        vector<string> path;// 临时数组path
        int n = s.length();// 字符串s的长度n

        auto 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 个数量的字符。