复盘 · LC 131 分割回文串

题目

题号：LeetCode 131
名称：分割回文串（Palindrome Partitioning）
难度：Medium
链接：leetcode.cn/problems/palindrome-partitioning/
今日代码：131-分割回文串/index.js

题意

把字符串 s 切成若干段，每一段都必须是回文，返回所有切法。

顺序固定，切点不同即不同方案（如 "aab" → [["a","a","b"],["aa","b"]]）。
边界：单字符必回文；全相同字符方案很多；空串一般不考。

涉及算法

标签	一句话
回溯分段	从 `start` 枚举结束下标 `i`，`s[start..i]` 是回文才继续
回文判定	双指针夹，或预处理 `dp[i][j]`

教程对照：19 · 递归心智与回溯框架；字符串回文手感见 23 · 字符串常考。

评价我的解法

你走了两阶段：先枚举出所有回文子串区间，再把能首尾相接的区间拼成覆盖 [0..n) 的方案。结果对，但绕且慢（约 6%），说明「能 AC」和「模板题」还差一层。

我的代码（摘自 131-分割回文串/index.js，不含测例）：

javascript

var partition = function (s) {
  const len = s.length;
  const charArr = s.split("");
  let tmpCharArr = [];
  const huiWeiArr = [];
  function isLegalArr(i, j) {
    if (tmpCharArr.length === 0) {
      return;
    }
    const otherChatArr = [...tmpCharArr].reverse();
    if (otherChatArr.join("") === tmpCharArr.join("")) {
      huiWeiArr.push([i, j, otherChatArr.join("")]);
    }
  }
  function dfs(i, j) {
    if (i >= len || j >= len) {
      return;
    }
    isLegalArr(i, j);
    tmpCharArr.push(charArr[j + 1]);
    dfs(i, j + 1);
    tmpCharArr.pop();
    if (j === i) {
      tmpCharArr = [];
      tmpCharArr.push(charArr[i + 1]);
      dfs(i + 1, i + 1);
      tmpCharArr.pop();
    }
  }
  dfs(0, -1);
  const resArr = [];
  const resSubStr = [];
  function findFull(j) {
    if (j === len - 1) {
      resArr.push([...resSubStr]);
      return;
    }
    for (const [tmpI, tmpJ, str] of huiWeiArr) {
      if (j + 1 === tmpI) {
        resSubStr.push(str);
        findFull(tmpJ);
        resSubStr.pop();
      }
    }
  }
  for (const [i, j, str] of huiWeiArr) {
    if (i === 0) {
      resSubStr.push(str);
      findFull(j);
      resSubStr.pop();
    }
  }

  return resArr;
};

问题点：

心智负担大：dfs(0,-1)、j === i 时清空再开下一段，读代码很难一次讲清；面试口述会卡。
回文判定贵：每次 reverse + join 比双指针差一截；预处理或边扩边判更稳。
二阶段拼接：findFull 每次线性扫 huiWeiArr 找下一段，常数差，和提交 6% 对得上。
命名：otherChatArr、huiWeiArr 不影响正确性，但不如 path / isPalindrome 好讲。

小结：题感（「段段回文」）对了，实现应收敛成一个从 start 出发的回溯，不要先物化全部回文再拼图。

最佳题解

经典「从 start 切」：

javascript

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const n = s.length;
  const res = [];
  const path = [];

  function isPalindrome(l, r) {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  }

  function dfs(start) {
    if (start === n) {
      res.push(path.slice());
      return;
    }
    for (let end = start; end < n; end++) {
      if (!isPalindrome(start, end)) continue;
      path.push(s.slice(start, end + 1));
      dfs(end + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
};

时间指数级（答案个数决定下界）+ 判定开销；空间 O(n) 递归深度。
为何更优：一次 DFS 完成「枚举切点 + 收集方案」；回文用双指针，逻辑可一句话讲完。
进阶：先 dp[i][j] 预处理是否回文，判定变 O(1)。

关联题目

题	为何相关
132. 分割回文串 II	同一题变「最少切几刀」→ DP
5. 最长回文子串	回文判定 / 中心扩展
22. 括号生成	同样是约束下的回溯枚举

一句话带走

分割回文串 = 从 start 枚举 end，段是回文才 dfs(end+1)；别先攒全图再拼接。

复盘 · LC 131 分割回文串 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​