07分割回文串

分割回文串

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

示例 1：

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

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

public List<List<String>> partition(String s) {
  char[] charArray = s.toCharArray();
  int len = s.length();

  // dp[i][j] 表示 s[i][j] 是否是回文
  boolean[][] dp = new boolean[len][len];
  for (int right = 0; right < len; right++) {
    for (int left = 0; left <= right; left++) {
      if(charArray[left] == charArray[right] && (right-left<=2 || dp[left+1][right-1])){
        dp[left][right] = true;
      }
    }
  }
  List<List<String>> res = new ArrayList<>();
  dfs(s,0,len,dp,new LinkedList<>(),res);
  return res;

}

private void dfs(String s , int index, int len, boolean[][] dp , Deque<String> path , List<List<String>> res){
  if(index == len){
    res.add(new ArrayList<>(path));
    return ;
  }

  for (int i = index; i < len ; i++) {
    // 如果 [index,i] 是回文, 则递归处理[i+1,len-1] 的字符串
    if(dp[index][i]){
      path.addLast(s.substring(index,i+1));
      dfs(s,i+1,len,dp,path,res);
      path.removeLast();
    }
  }
}