一、题目

给你一个字符串 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。那么状态转移方程如下：
131. 分割回文串 - 图1

三、代码

  1. class Solution {
  2.     private boolean[][] dp;
  3.     private List<List<String>> ans = new ArrayList();
  4.     private List<String> temp = new ArrayList();
  6.     public List<List<String>> partition(String s) {
  7.         dp = new boolean[s.length()][s.length()];
  8.         for (int i = s.length() - 1; i >= 0; i--) {    // 动态规划先将所有的回文串找出来，记忆住
  9.             for (int j = i; j < s.length(); j++) {
  10.                 if (i == j) {
  11.                     dp[i][j] = true;
  12.                 } else if (j - i == 1) {
  13.                     dp[i][j] = s.charAt(i) == s.charAt(j);
  14.                 } else {
  15.                     dp[i][j] = (s.charAt(i) == s.charAt(j)) && (dp[i+1][j-1]);
  16.                 }
  17.             }
  18.         }
  19.         dfs(s, 0);    // 将其看作树进行搜索
  20.         return ans;
  21.     }
  22.     private void dfs(String s, int i) {
  23.         if (i >= s.length() ) {    // 搜索完一种可行方案
  24.             ans.add(new ArrayList(temp));
  25.         }
  26.         for (int j = i; j < s.length(); j++) {
  27.             if (dp[i][j]) {    // 根据记忆化来判断s[i, j]是否为回文串
  28.                 temp.add(s.substring(i, j+1));
  29.                 dfs(s, j+1);
  30.                 temp.remove(temp.size()-1);
  31.             }
  32.         }
  33.     }
  34. }

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