【每日算法】131. 分割回文串

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。
------ 算法：资深前端开发者的进阶引擎

LeetCode 131. 分割回文串

1. 题目描述

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

一个回文串是一个正读和反读都相同的字符串。

示例：

输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例：

输入：s = “a” 输出：[[“a”]]

2. 问题分析

这是一道经典的组合/分割问题。我们需要把一个字符串切割成若干个子串，每个子串都必须是回文串，并找出所有可能的切割方式。

关键点：

1. 找出所有可能性：暗示我们需要使用回溯（DFS）算法进行搜索。
2. 有效性判断：在每一步尝试切割时，必须确保当前切割出的子串是回文串。
3. 抽象理解：这可以类比为在一串字符的“间隙”中放置“切割点”。从起点开始，每次决定“切多长”（即下一个回文子串到哪里结束），然后递归处理剩下的部分。

前端视角联想：

• 路由权限配置：将用户完整的访问路径拆分为多个权限段，每一段都必须符合规则，类似于将字符串分割为多个有效的回文子路径。
• 富文本或Markdown解析：将一段文本流拆解为不同语义的块（如标题、段落、代码块），每个块都有其特定的语法规则（类似于回文判断）。

3. 解题思路

3.1 核心思想：回溯 + 剪枝

思路（回溯法）：

1. 定义状态：当前搜索的起始索引startIndex，以及当前路径path（已收集的回文子串列表）。
2. 递归终止条件：当startIndex移动到字符串末尾时，说明找到了一组完整的分割方案，将path加入结果集。
3. 单层搜索逻辑：
   • 从startIndex开始，尝试所有可能的结束位置i（即子串s[startIndex, i]）。
   • 判断该子串是否是回文串：
     • 如果是，则将其加入path。
     • 然后递归处理剩下的部分（startIndex = i + 1）。
     • 递归返回后，进行“回溯”，将刚才加入的子串从path中移除，以尝试其他切割可能。
   • 如果不是回文串，直接跳过（剪枝），不再向下递归，因为后续分割都是基于当前无效前缀进行的。

3.2 回文判断的优化：动态规划预处理

在回溯过程中，我们会反复判断同一个子串是否为回文（例如，从不同路径访问s[i..j]）。可以通过动态规划（DP）预处理一个二维表dp[i][j]，表示s[i..j]是否是回文串。

• 状态转移方程：
  • dp[i][j] = true， 如果i == j（单个字符）
  • dp[i][j] = (s[i] == s[j])， 如果j - i == 1（相邻两个字符）
  • dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]， 如果j - i > 1
• 这样，在回溯过程中判断回文时，可以O(1)时间查表。

最优解：回溯 + 动态规划预处理。这是解决此题的标准且高效的方法，兼顾了清晰性和性能。

4. 各思路代码实现 (JavaScript)

4.1 思路一：回溯 + 双指针判断回文（直观解法）

/** * @param {string} s * @return {string[][]} */varpartition=function(s){constresult=[];constpath=[];// 辅助函数：双指针判断子串 s[left..right] 是否为回文constisPalindrome=(str,left,right)=>{while(left<right){if(str[left]!==str[right]){returnfalse;}left++;right--;}returntrue;};constbacktrack=(startIdx)=>{// 终止条件：如果起始位置已到字符串末尾if(startIdx>=s.length){result.push([...path]);// 复制当前路径到结果return;}for(leti=startIdx;i<s.length;i++){// 判断当前截取的子串 s[startIdx..i] 是否是回文if(isPalindrome(s,startIdx,i)){// 是回文，则加入路径path.push(s.substring(startIdx,i+1));// 递归处理剩余部分 s[i+1..]backtrack(i+1);// 回溯，撤销选择path.pop();}// 如果不是回文，则直接跳过当前循环（剪枝）}};backtrack(0);returnresult;};

4.2 思路二：回溯 + 动态规划预处理回文（优化解法）

/** * @param {string} s * @return {string[][]} */varpartition=function(s){constlen=s.length;constresult=[];constpath=[];// 1. 动态规划预处理回文表 dp[i][j]// dp[i][j] 表示 s[i..j] 是否为回文串 (i <= j)constdp=newArray(len).fill(false).map(()=>newArray(len).fill(false));// 注意填表顺序：由于 dp[i][j] 依赖于 dp[i+1][j-1]，所以 i 从后往前，j 从 i 往后for(leti=len-1;i>=0;i--){for(letj=i;j<len;j++){if(i===j){dp[i][j]=true;// 单个字符}elseif(j-i===1){dp[i][j]=(s[i]===s[j]);// 相邻两个字符}else{dp[i][j]=(s[i]===s[j])&&dp[i+1][j-1];}}}// 2. 回溯函数constbacktrack=(startIdx)=>{if(startIdx>=len){result.push([...path]);return;}for(leti=startIdx;i<len;i++){// O(1) 查询是否为回文if(dp[startIdx][i]){path.push(s.substring(startIdx,i+1));backtrack(i+1);path.pop();}}};backtrack(0);returnresult;};

5. 各实现思路的复杂度、优缺点对比

6. 总结

6.1 核心收获

LeetCode 131 题是回溯算法的一个典型应用。它清晰地展示了回溯法的核心框架：

1. 做出选择（切割出一个回文子串）。
2. 递归探索（处理剩余字符串）。
3. 撤销选择（回溯以尝试其他长度）。

同时，它引入了空间换时间的优化思想（DP预处理），这是算法工程中极其重要的策略。

6.2 前端实际应用场景

1. 代码/资源分割 (Code Splitting)：

   • 在 Webpack 等构建工具中，将整个应用代码分割成多个“块”(chunk)。这类似于将字符串s（整个应用）分割成多个子串（chunk），每个 chunk 必须是“有效的”（可独立加载和运行）。分割策略的算法思维与此相通。

2. 路由设计与权限控制：

   • 一个复杂的 URL 路径/admin/user/list可能需要被分割为[‘admin‘， ’user‘， ’list‘]，并逐级校验每一段对应的模块权限是否有效（“回文”在此类比为“有效权限模块”）。设计这种动态路由匹配和鉴权系统时，需要类似的递归分解与验证思想。

3. 富文本/模板解析：

   • 解析 Markdown 或自定义模板语法时，需要将文本流扫描分割成不同的 token（如标题、加粗文本、代码块）。识别每一段 token 的起始和结束标志，并验证其语法的正确性，这个过程就是“分割”与“有效性判断”的结合。

4. UI 组件树的递归渲染与更新：

   • React/Vue 的虚拟 DOM Diff 算法，本质上是在一棵树结构上进行“分割”比较。虽然数据结构不同，但其递归遍历、验证子节点是否可复用（类似于判断是否为“有效”子结构）的核心思想是高度一致的。