LeetCode 131 分割回文串 是一道非常经典的 回溯算法Backtracking 题目。题目描述给定一个字符串“s”将“s” 分割成一些子串使每个子串都是回文串。返回“s” 所有可能的分割方案。示例输入: “aab”输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]解题思路回溯DFS从字符串的起始位置开始依次截取子串。回文判断每截取一个子串判断它是否为回文。如果是回文则将其加入当前方案“path”并递归处理剩余子串。递归结束后进行回溯将该子串从方案中移除尝试其他分割方式。终止条件当起始位置到达字符串末尾时说明找到了一种合法分割将当前方案加入结果集。优化可以用动态规划DP预先计算所有子串是否为回文避免每次递归时重复判断下面提供两个版本。方法一回溯 双指针判断回文简洁直观/**param {string} sreturn {string[][]}*/var partition function(s) {const result [];const path [];// 双指针判断回文function isPalindrome(left, right) {while (left right) {if (s[left] ! s[right]) return false;left;right–;}return true;}// 回溯函数function backtrack(start) {// 递归终止遍历完整个字符串if (start s.length) {result.push([…path]);return;}// 从 start 开始尝试分割 for (let i start; i s.length; i) { if (isPalindrome(start, i)) { // 截取子串 [start, i] path.push(s.substring(start, i 1)); // 递归处理剩余部分 backtrack(i 1); // 回溯 path.pop(); } }}backtrack(0);return result;};方法二回溯 DP 预处理性能更优适合长字符串/**param {string} sreturn {string[][]}*/var partition function(s) {const n s.length;// 1. DP 预处理dp[i][j] 表示 s[i…j] 是否为回文const dp Array.from({ length: n }, () Array(n).fill(false));for (let i 0; i n; i) dp[i][i] true; // 单个字符是回文for (let i n - 1; i 0; i–) {for (let j i 1; j n; j) {if (s[i] s[j]) {dp[i][j] (j - i 1) ? true : dp[i 1][j - 1];}}}// 2. 回溯const result [];const path [];function backtrack(start) {if (start n) {result.push([…path]);return;}for (let i start; i n; i) { if (dp[start][i]) { path.push(s.substring(start, i 1)); backtrack(i 1); path.pop(); } }}backtrack(0);return result;};复杂度分析时间复杂度方法一约 O(n \cdot 2^n) 共有 2^{n-1} 种分割方式每次判断回文 O(n) 。方法二DP 预处理 O(n^2) 回溯过程同样是指数级但回文判断降为 O(1) 。空间复杂度 O(n) 递归调用栈以及存储路径的深度DP 数组额外占用 O(n^2) 。如果你需要我帮你把这段代码改成 TypeScript 版本或者想看 LeetCode 132分割回文串 II求最小分割次数 的动态规划解法随时告诉我
