分割回文串

题目链接

LeetCode 131: 分割回文串

题目

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

例如：

输入: "aab"
输出:
[
  ["a","a","b"],
  ["aa","b"]
]

思路

1. 动态规划预处理：首先使用动态规划预处理出所有的回文子串。我们使用一个二维数组 dp，其中 dp[i][j] 表示子串 s[i:j+1] 是否为回文。预处理的时间复杂度为 $O(n^2)$。

2. 回溯算法：在回溯过程中，通过 dp 数组快速判断子串是否为回文。我们从字符串的起始位置开始尝试分割，对于每一个位置，若子串是回文，则将其加入当前路径，并继续对剩余部分进行递归。当到达字符串末尾时，将当前路径加入结果集。

解题方法

1. 动态规划预处理

const dp = Array.from(Array(n), () => Array(n).fill(false));
for (let right = 0; right < n; right++) {
  for (let left = 0; left <= right; left++) {
    if (s[left] === s[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
      dp[left][right] = true;
    }
  }
}

• dp 数组初始化为 false。
• 双重循环填充 dp 数组。s[left] === s[right] 表示两端字符相同，如果这两个字符相邻或中间部分是回文（即 dp[left + 1][right - 1] 为 true），则 dp[left][right] 设为 true。

2. 回溯函数

function backTracking(start, path) {
  if (start === s.length) {
    result.push([...path]);
    return;
  }

  for (let end = start; end < s.length; end++) {
    if (dp[start][end]) {
      path.push(s.slice(start, end + 1));
      backTracking(end + 1, path);
      path.pop();
    }
  }
}

• 回溯函数 backTracking 从起始位置 start 开始分割。
• 如果 start 到 end 的子串是回文（dp[start][end] 为 true），将该子串加入路径，并继续递归分割剩余部分。
• 使用 dp 表来判断子串是否为回文，避免重复计算。

代码

const partition = function(s) {
  const result = [];
  const path = [];
  const n = s.length;

  // 预处理，使用动态规划记录所有子串是否为回文
  const dp = Array.from(Array(n), () => Array(n).fill(false));
  for (let right = 0; right < n; right++) {
    for (let left = 0; left <= right; left++) {
      if (s[left] === s[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
        dp[left][right] = true;
      }
    }
  }

  function backTracking(start, path) {
    if (start === s.length) {
      result.push([...path]);
      return;
    }

    for (let end = start; end < s.length; end++) {
      if (dp[start][end]) {
        path.push(s.slice(start, end + 1));
        backTracking(end + 1, path);
        path.pop();
      }
    }
  }

  backTracking(0, path);
  return result;
};

// 测试
const s = "aab";
console.log(partition(s)); 
// 输出: [["a", "a", "b"], ["aa", "b"]]

复杂度分析

• 时间复杂度：$O(n \cdot 2^n)$，其中 $n$ 是字符串的长度。预处理阶段的时间复杂度为 $O(n^2)$，回溯阶段的时间复杂度为 $O(n \cdot 2^n)$。
• 空间复杂度：$O(n^2)$。主要用于存储动态规划表 dp 和递归调用栈的开销。