【LeetCode刷题日记】131.分割回文串，动态规划优化

个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰这里祝大家周末快乐现在是我们的每日刷题环节主要是回溯算法相关的让我们一起看看吧。摘要本文探讨了LeetCode 131题“分割回文串”的解法通过回溯算法结合动态规划预处理优化求解。题目要求将字符串分割为若干回文子串返回所有可能的分割方案。关键步骤回文判断使用双指针或动态规划预处理二维数组dp[i][j]标记子串s[i..j]是否为回文。回溯切割从起始位置start开始遍历若子串s[start..i]是回文通过dp快速查询则递归处理剩余部分i1回溯时撤销选择。动态规划优化通过递推式dp[i][j] (s[i]s[j]) (j-i≤2 || dp[i1][j-1])从短子串向长子串推导避免重复计算。示例字符串aab的分割结果为[ [a,a,b], [aa,b] ]。代码通过预处理dp数组和回溯搜索高效生成所有解。总结结合动态规划预处理与回溯剪枝显著提升效率时间复杂度为O(n·2ⁿ)适用于短字符串长度≤16。题目背景131.分割回文串给你一个字符串s请你将s分割成一些 子串使每个子串都是回文串。返回s所有可能的分割方案。示例 1输入s aab输出[[a,a,b],[aa,b]]示例 2输入s a输出[[a]]提示1 s.length 16s仅由小写英文字母组成题目分析这道题题目很简短目标也很明确主要操作是分割分割的目的是得到回文串那我们肯定要知道什么是回文串怎么判断是不是回文串这样才能决定我们如何分割。其实我们在前面做题的时候也遇到过回文串。回文串处理回文串Palindrome是指一个正着读和反着读都一样的字符串。简单理解把字符串反过来写和原来的字符串完全相同。字符串是否回文原因aba✅正a b a反a b aabc❌正a b c反c b aabba✅正a b b a反a b b a那么该如何判断呢前面我们就是利用双指针的方法进行判断的这里顺便复习一下。判断方法方法1双指针法java boolean isPalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; }方法2反转比较java boolean isPalindrome(String s) { String reversed new StringBuilder(s).reverse().toString(); return s.equals(reversed); }切割思路本题这涉及到两个关键问题切割问题有不同的切割方式判断回文这种题目想用for循环暴力解法可能都不那么容易写出来所以要换一种暴力的方式就是回溯。一些同学可能想不清楚 回溯究竟是如何切割字符串呢我们来分析一下切割其实切割问题类似组合问题。例如对于字符串abcdef组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段.....。所以切割问题也可以抽象为一棵树形结构如图递归用来纵向遍历for循环用来横向遍历切割线就是图中的红线切割到字符串的结尾位置说明找到了一个切割方法。此时可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多回溯三部曲递归函数参数全局变量数组path存放切割后回文的子串二维数组result存放结果集。 这两个参数可以放到函数参数里本题递归函数参数还需要startIndex因为切割过的地方不能重复切割和组合问题也是保持一致的。在前面我们深入探讨了组合问题什么时候需要startIndex什么时候不需要startIndex。递归函数终止条件从树形结构的图中可以看出切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。那么在代码里什么是切割线呢在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。单层搜索的逻辑来看看在递归循环中如何截取子串呢在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文如果是回文就加入在path中path用来记录切割过的回文子串。代码如下for (int i startIndex; i s.size(); i) { if (isPalindrome(s, startIndex, i)) { // 是回文子串 // 获取[startIndex,i]在s中的子串 string str s.substr(startIndex, i - startIndex 1); path.push_back(str); } else { // 如果不是则直接跳过 continue; } backtracking(s, i 1); // 寻找i1为起始位置的子串 path.pop_back(); // 回溯过程弹出本次已经添加的子串 }注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。题目答案这里我们答案思路就是先判断这个字符串分割之后预先计算出字符串s中所有可能的子串是否是回文串并存储在二维数组dp中供后续回溯算法快速查询。想象你有一个字符串aab你想知道每个子串是不是回文子串[0,0]→a是不是回文子串[0,1]→aa是不是回文子串[1,2]→ab是不是回文...这段代码一次性把所有子串的判断结果都算出来存在一个表格里。dp[i][j]表示从索引 i 到索引 j 的子串包含两端是不是回文串例如s aab索引0:a, 1:a, 2:bdp[i][j]j0j1j2i0a✅aa✅aab❌i1-a✅ab❌i2--b✅核心递推公式java if (s.charAt(i) s.charAt(j) (j - i 2 || dp[i1][j-1])) { dp[i][j] true; }这行代码的逻辑是首尾字符必须相等s.charAt(i) s.charAt(j)满足以下任一条件长度 ≤ 2即j - i 2a、aa、aba这类短串直接判断去掉首尾后中间部分是回文dp[i1][j-1] true以s abcba判断dp[0][4]整个串abcba为例text步骤1: 比较首尾 a a ✅ 步骤2: 长度 2看中间部分 dp[1][3] 是否是回文 ↓ 中间是 bcb 步骤3: 比较首尾 b b ✅ 步骤4: 长度 2看中间部分 dp[2][2] 是否是回文 ↓ 中间是 c 步骤5: 单个字符一定是回文 ✅ ↓ 回溯 dp[2][2] true → dp[1][3] true → dp[0][4] trueimport java.util.ArrayList; import java.util.List; class Solution { public ListListString partition(String s) { ListListString result new ArrayList(); if (s null || s.length() 0) { return result; } int n s.length(); // dp[i][j] 表示 s[i..j] 是否是回文串 boolean[][] dp new boolean[n][n]; // 初始化dp数组 for (int j 0; j n; j) { for (int i 0; i j; i) { if (s.charAt(i) s.charAt(j) (j - i 2 || dp[i1][j-1])) { dp[i][j] true; } } } // 回溯搜索所有分割方案 backtrack(s, 0, new ArrayList(), result, dp); return result; } private void backtrack(String s, int start, ListString path, ListListString result, boolean[][] dp) { // 已经分割到末尾找到一种有效分割 if (start s.length()) { result.add(new ArrayList(path)); return; } for (int end start; end s.length(); end) { // 如果当前子串 [start, end] 是回文串 if (dp[start][end]) { path.add(s.substring(start, end 1)); backtrack(s, end 1, path, result, dp); path.remove(path.size() - 1); // 回溯 } } } }这里其实有动态规划的优化思路如果只知道首位元素是相同的根据这个dp[i1][j-1] true为什么就能知道内部就是回文的了这不就是向内一层吗触及了动态规划的核心逻辑。简单直接的回答是是的这就是向内一层。这就像一个“剥洋葱”的过程或者数学归纳法。因为我们通过dp[i1][j-1]这个状态已经假设并信赖了“内部”已经是回文所以只要最外层两个字符相等整个字符串就一定是回文。用一个具体的例子和递推的原理来解释例子判断s abcba的dp[0][4]我们想知道abcba是不是回文。根据问题我们的逻辑是最外层s[0] as[4] a它们相等。 ✅向内一层我们去看dp[1][3]。这个格子代表子串bcb的状态。关键来了dp[1][3]是怎么知道的dp[1][3]的求解过程完全一样它的最外层s[1] bs[3] b它们相等。 ✅它的向内一层去看dp[2][2]这个格子代表子串c。dp[2][2]又怎么知道的因为i j所以j - i 0 2根据我们的代码j - i 2dp[2][2]直接被标记为true。这是基本情况。现在我们再从内向外“递推”回去第3层 (最内层)因为c是单个字符所以dp[2][2] true。第2层因为s[1] s[3]并且内部的dp[2][2] true所以dp[1][3] true。此时我们知道bcb是回文了第1层 (最外层)因为s[0] s[4]并且内部的dp[1][3] true所以dp[0][4] true。总结问题为什么根据dp[i1][j-1] true就能知道内部就是回文的了答因为dp[i1][j-1]这个状态本身就是通过同样的逻辑一层一层向内验证得来的。它是一个已经被验证过的、正确的结论。我们基于这个正确的“内部结论”加上“外层相等”这个条件就能推导出“整个”是回文的。这个过程完美地体现了动态规划的无后效性和最优子结构最优子结构一个字符串是不是回文取决于“去掉首尾后的子串”是不是回文。无后效性dp[i1][j-1]的状态一旦确定就不会再改变我们可以放心地使用它。所以dp的核心就是利用内层已经算好的结果来推导外层从而避免重复劳动。这正是它高效的原因结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励