力扣131 js实现

力扣131题（分割回文串）的JavaScript实现

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

示例
输入："aab"
输出：

[
  ["a","a","b"],
  ["aa","b"]
]

解题思路

回溯法结合动态规划预处理回文串。

1. 动态规划预处理：生成一个二维数组 dp，dp[i][j] 表示 s[i...j] 是否为回文串。
2. 回溯搜索：从字符串起始位置开始，利用预处理结果快速判断可分割点，递归生成所有合法分割方案。

JavaScript代码实现

/
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(true));
    // 动态规划预处理回文串
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; j++) {
            dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
        }
    }

    const res = [];
    const backtrack = (start, path) => {
        if (start === n) {
            res.push([...path]);
            return;
        }
        for (let end = start; end < n; end++) {
            if (dp[start][end]) {
                path.push(s.slice(start, end + 1));
                backtrack(end + 1, path);
                path.pop();
            }
        }
    };
    backtrack(0, []);
    return res;
};

代码解释

1. 动态规划预处理

   • 初始化 dp 数组，dp[i][j] 表示子串 s[i...j] 是否为回文。
   • 从后向前遍历，利用状态转移方程 dp[i][j] = s[i] === s[j] && dp[i+1][j-1] 填充 dp。

2. 回溯搜索

   • 从起始位置 start 开始，枚举所有可能的结束位置 end。
   • 若 s[start...end] 是回文（通过 dp[start][end] 判断），将其加入当前路径 path，并递归处理剩余子串 s[end+1...]。
   • 回溯时弹出 path 末尾元素，继续尝试其他分割点。

3. 终止条件

   • 当 start 达到字符串末尾时，将当前路径 path 加入结果集 res。

复杂度分析

• 时间复杂度：O(n·2ⁿ)，其中 n 为字符串长度。最坏情况下所有子串均为回文，共有 2ⁿ 种分割方案。
• 空间复杂度：O(n²)，存储 dp 数组所需空间。