leetcode 131. 分割回文串

一、题目

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

回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

二、解法

思路：回溯。
其中需要判断s[i:j]是否是回文串。可以用动态规划来存储。

class Solution {
    List> ans=new ArrayList<>();
    List cur=new ArrayList<>();
    boolean[][] f;

    public List> partition(String s) {
        int n=s.length();
        f=new boolean[n][n];
        for(int i=0;i=0;i--){
            for(int j=i+1;j(cur));
            return;
        }
        for(int i=index;i