题目

131. 分割回文串
难度中等509收藏分享切换为英文接收动态反馈
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

思路

搜索函数
从当前起点向后找，如果是回文，那就把结果放入，然后递归的找
如果满足结果，最后就会放入最终结果的数组

结束当前步的搜索就会把这个结果pop出来，相当于是一次回溯操作

void dfs(const string& s, int i) {
    if (i == n) {
        ret.push_back(ans);
        return;
    }
    for (int j = i; j < n; ++j) {
        if (f[i][j]) {
            ans.push_back(s.substr(i, j - i + 1));
            dfs(s, j + 1);
            ans.pop_back();
        }
    }
}

在搜索的时候需要快速的判断i，j段的字符串是不是回文
所以使用了动态规划直接存储