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

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

示例:

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

Solution

参考 @liuyubobobo 、@liweiwei1419 、代码随想录

思考如何根据这棵递归树编码：

1、每一个结点表示剩余没有扫描到的字符串，产生分支是截取了剩余字符串的前缀；

2、产生前缀字符串的时候，判断前缀字符串是否是回文。

• 如果前缀字符串是回文，则可以产生分支和结点；
• 如果前缀字符串不是回文，则不产生分支和结点，这一步是剪枝操作。

3、在叶子结点是空字符串的时候结算

// @lc code=start
class Solution {
private:
    vector<vector<string>> res;

    void dfs(const string& s, int l, vector<string>& cur){
        if(l==s.size()){
            res.push_back(cur);
            return;
        }

        for(int r=l; r<s.size(); ++r){
            if(ispalindrome(s, l, r)){
                cur.push_back(s.substr(l, r-l+1));
                dfs(s, r+1, cur);
                cur.pop_back();
            }
        }
    }

    bool ispalindrome(const string& s, int l, int r){
        while(l<=r){
            if(s[l] != s[r])
                return false;
            l++, r--;
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        vector<string> cur;
        dfs(s, 0, cur);
        return res;
    }
};
// @lc code=end

题目难点：

• 切割问题可以抽象为组合问题
• 如何模拟那些切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文