一、题目

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

点击查看原题

二、思路

       首先考虑如何形成所有的分割方案，可以考虑使用dfs的方法，将每种方案看作从根节点搜索到每个叶子节点的路径，将这些路径保存下来即为题目所求的解。
       那么如果判断字符串s中从位置i到位置j为回文串呢？
       首先根据回文串的特性，可以得知回文串中s[i, j]中的子串s[i+1, j-1]也为回文串（不考虑边界情况，因为去掉了两边相同的字符）。考虑特殊情况：

1、当i=j时，单个字符一定是回文串
2、当i+1=j时，如果s[i]==s[j]，那么s[i, j]为回文串
3、其他情况，如果s[i]==s[j]且s[i+1, j-1]为回文串，那么s[i, j]为回文串

       采用记忆化可以减少对重复子问题的计算，令数组dp[i][j]表示s[i, j]是否为字符串，是为true。那么状态转移方程如下：
d p [ i ] [ j ] = { t r u e , i = = j s [ i ] = = s [ j ] , i + 1 = = j ( s [ i ] = = s [ j ] ) & & ( d p [ i + 1 ] [ j − 1 ] = = t r u e ) , e l s e dp[i][j]=\left\{ \begin{aligned} true&,& i==j\\ s[i]==s[j] &,& i+1==j \\ (s[i]==s[j])\&\&(dp[i+1][j-1] ==true)&,& else\\ \end{aligned} \right. dp[i][j]=⎩⎪⎨⎪⎧​trues[i]==s[j](s[i]==s[j])&&(dp[i+1][j−1]==true)​,,,​i==ji+1==jelse​

三、代码

class Solution {
    private boolean[][] dp;
    private List<List<String>> ans = new ArrayList();
    private List<String> temp = new ArrayList();

    public List<List<String>> partition(String s) {
        dp = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {	// 动态规划先将所有的回文串找出来，记忆住
            for (int j = i; j < s.length(); j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (j - i == 1) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j)) && (dp[i+1][j-1]);
                }
            }
        }
        dfs(s, 0);	// 将其看作树进行搜索
        return ans;
    }
    private void dfs(String s, int i) {
        if (i >= s.length() ) {	// 搜索完一种可行方案
            ans.add(new ArrayList(temp));
        }
        for (int j = i; j < s.length(); j++) {
            if (dp[i][j]) {	// 根据记忆化来判断s[i, j]是否为回文串
                temp.add(s.substring(i, j+1));
                dfs(s, j+1);
                temp.remove(temp.size()-1);
            }
        }
    }
}

       时间复杂度为O(n*2ⁿ)，2为为搜索树的时间复杂度，而n为每次保存可行方案的时间。空间复杂度为O(n²)。