本文共 2229 字，大约阅读时间需要 7 分钟。
回文分割问题是将一个字符串分割成尽可能多的回文子串，并返回所有可能的分割方案。解决这个问题的关键在于预处理回文子串信息，并通过回溯方法列举所有可能的分割方案。
预处理回文信息：使用动态规划预处理所有可能的子串是否为回文。创建一个二维数组dp，dp[i][j]表示子串s[i...j]是否为回文。当子串长度为1时，总是回文；长度为2时，判断两端字符是否相同；长度大于2时，判断中间是否为回文。
回溯生成分割方案：从字符串的开头开始，尝试每一个可能的右边界j，判断subString是否为回文。如果是，将其作为分割的一部分，并递归处理剩余的字符串，直到最后一个字符。这样可以生成所有可能的分割方案。
初始化：读取输入字符串，计算其长度，准备分割结果列表和辅助数组dp。
填充回文信息：遍历所有可能的子串，使用动态规划填充dp数组。对于长度小于等于2的子串直接比较字符；对于更长的子串，检查中间部分是否为回文。
回溯分割：使用递归函数从字符串开头开始分割。对于每个起始点i，尝试所有可能的终止点j，只要subString是回文，就将其作为分割添加到结果中，并递归处理剩余部分。
剪枝：如果在分割过程中遇到无法满足回文的子串，跳过这个路径；如果当前分割已经完成或无法继续，终止递归，减少重复计算。
结果管理：确保每一次回溯都能正确记录分割方案，避免遗漏任何一种可能。
import java.util.ArrayList;import java.util.List;public class Solution { public List > partition(String s) { int n = s.length(); if (n == 0) { return new ArrayList<>(); } char[] arrStr = s.toCharArray(); boolean[][] dp = new boolean[n][n]; // 预处理回文数组dp for (int i = 0; i < n; i++) { dp[i][i] = true; // 单个字符是回文 if (i < n - 1) { dp[i][i + 1] = (arrStr[i] == arrStr[i + 1]); } } for (int i = 0; i < n; i++) { for (int j = i + 2; j < n; j++) { if (arrStr[i] == arrStr[j] && dp[i + 1][j - 1]) { dp[i][j] = true; } else { dp[i][j] = false; } } } List > result = new ArrayList<>(); List currentPath = new ArrayList<>(); // 回溯函数 backTrack(0, dp, 0, arrStr, n, result, currentPath) ; return result; } private void backTrack(int start, boolean[][] dp, int p, char[] arr, int n, List > result, List currentPath) { if (start >= n) { result.add(new ArrayList<>(currentPath)); return; } for (int i = start; i < n; i++) { if (dp[start][i] && (i == start || p == i)) { currentPath.add(arr[start..i+1]); backTrack(i + 1, dp, i, arr, n, result, currentPath); currentPath.remove(); } } }}
Dp数组初始化：dp[i][j]由两步填充。首先单个字符是回文；接着比较两端字符，以及中间部分是否是回文，以确定更长子串是否为回文。
回溯函数：从当前位置开始，尝试所有可能的终止位置i，如果subString为回文，分割添加到路径，并递归处理下一个位置。这种方法可以有效生成所有可能的分割方案。
这样的方法能够高效地分割字符串，并生成所有可能的回文分割方案，适用于字符串长度不超过16的情况。
转载地址：http://chgyk.baihongyu.com/