一、 回文串基础概念回文串正读和反读完全相同的字符串。a ✅ 单字符均是回文 aba ✅ 奇数长度回文中心是 b abba ✅ 偶数长度回文中心在两个 b 之间 abc ❌ 不是回文关键性质贯穿所有题目单个字符一定是回文串若s[i] s[j]且s[i1..j-1]是回文 →s[i..j]是回文回文串去掉首尾两个字符后仍是回文串二、 两大核心算法️ 算法一中心扩展法思路枚举每一个中心点向两边扩展只要两端字符相等就继续。⚠️ 注意中心点分两种情况奇数长度中心是某个字符如aba中心是b偶数长度中心是两个字符之间如abba中心在两个b之间/** * 中心扩展法通用模板 * 以 (left, right) 为中心向外扩展返回最长回文子串 */privateStringexpandAroundCenter(Strings,intleft,intright){while(left0rights.length()s.charAt(left)s.charAt(right)){left--;right;}// 循环结束时 left 和 right 已经越界所以截取 [left1, right-1]returns.substring(left1,right);}// 调用方式for(inti0;is.length();i){StringoddexpandAroundCenter(s,i,i);// 奇数长度以 i 为中心StringevenexpandAroundCenter(s,i,i1);// 偶数长度以 i,i1 为中心}时间复杂度O(n²) 空间复杂度O(1)️ 算法二动态规划DP思路用二维dp[i][j]表示s[i..j]是否为回文串。状态转移方程dp[i][j] true, 当 s[i] s[j] 且 (j-i2 或 dp[i1][j-1]true) dp[i][j] false, 当 s[i] ! s[j]初始化所有dp[i][i] true单字符是回文/** * 动态规划通用模板 */intns.length();boolean[][]dpnewboolean[n][n];// ⚠️ 重要必须按子串长度从小到大填表不能直接双重 i,j 循环for(intin-1;i0;i--){// i 从右往左for(intji;jn;j){// j 从左往右保证 j iif(s.charAt(i)s.charAt(j)){// 长度 2或者内部子串也是回文dp[i][j](j-i2)||dp[i1][j-1];}else{dp[i][j]false;}}}时间复杂度O(n²) 空间复杂度O(n²)三、 核心题目精讲✅ LC 125 — 验证回文串Easy题意只考虑字母和数字字符忽略大小写判断是否回文。考点双指针 字符过滤publicbooleanisPalindrome(Strings){intleft0,rights.length()-1;while(leftright){// 跳过非字母数字字符while(leftright!Character.isLetterOrDigit(s.charAt(left)))left;while(leftright!Character.isLetterOrDigit(s.charAt(right)))right--;// 忽略大小写比较if(Character.toLowerCase(s.charAt(left))!Character.toLowerCase(s.charAt(right))){returnfalse;}left;right--;}returntrue;}✅ LC 409 — 最长回文串Easy题意给定字符集合用这些字符能组成的最长回文串长度是多少核心思路偶数个的字符可以全部用上奇数个的字符只能用count - 1个凑成偶数最终可以在中间放一个奇数字符publicintlongestPalindrome(Strings){int[]freqnewint[128];for(charc:s.toCharArray())freq[c];intlength0;booleanhasOddfalse;for(intcount:freq){length(count/2)*2;// 取偶数部分if(count%21)hasOddtrue;}returnhasOdd?length1:length;// 有奇数字符可以放中间}✅ LC 680 — 验证回文串 IIEasy题意最多删除一个字符判断是否能构成回文串。核心思路双指针遇到不匹配时尝试跳过左或右字符验证剩余部分是否回文。publicbooleanvalidPalindrome(Strings){intleft0,rights.length()-1;while(leftright){if(s.charAt(left)!s.charAt(right)){// 两种跳法任意一种满足即可returnisPalin(s,left1,right)||isPalin(s,left,right-1);}left;right--;}returntrue;}// 辅助函数验证 s[l..r] 是否回文privatebooleanisPalin(Strings,intl,intr){while(lr){if(s.charAt(l)!s.charAt(r--))returnfalse;}returntrue;}✅ LC 5 — 最长回文子串Medium题意找出字符串中最长的回文子串。解法1中心扩展法推荐publicStringlongestPalindrome(Strings){Stringresult;for(inti0;is.length();i){Stringoddexpand(s,i,i);// 奇数中心Stringevenexpand(s,i,i1);// 偶数中心if(odd.length()result.length())resultodd;if(even.length()result.length())resulteven;}returnresult;}privateStringexpand(Strings,intl,intr){while(l0rs.length()s.charAt(l)s.charAt(r)){l--;r;}returns.substring(l1,r);}解法2动态规划publicStringlongestPalindrome(Strings){intns.length(),start0,maxLen1;boolean[][]dpnewboolean[n][n];for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)(j-i2||dp[i1][j-1])){dp[i][j]true;if(j-i1maxLen){maxLenj-i1;starti;}}}}returns.substring(start,startmaxLen);}✅ LC 647 — 回文子串Medium题意计算字符串中共有多少个回文子串。解法1中心扩展法推荐publicintcountSubstrings(Strings){intcount0;for(inti0;is.length();i){countexpandCount(s,i,i);// 奇数countexpandCount(s,i,i1);// 偶数}returncount;}privateintexpandCount(Strings,intl,intr){intcount0;while(l0rs.length()s.charAt(l)s.charAt(r)){count;l--;r;}returncount;}解法2动态规划publicintcountSubstrings(Strings){intns.length(),count0;boolean[][]dpnewboolean[n][n];for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)(j-i2||dp[i1][j-1])){dp[i][j]true;count;}}}returncount;}✅ LC 516 — 最长回文子序列Medium题意找最长的回文子序列长度子序列不要求连续。⚠️ 注意区别子串连续vs子序列不连续DP 定义dp[i][j]s[i..j]中最长回文子序列的长度publicintlongestPalindromeSubseq(Strings){intns.length();int[][]dpnewint[n][n];// 初始化每个单字符是长度为1的回文子序列for(inti0;in;i)dp[i][i]1;for(intin-1;i0;i--){for(intji1;jn;j){if(s.charAt(i)s.charAt(j)){dp[i][j]dp[i1][j-1]2;// 两端字符相同加入子序列}else{// 两端不同取去掉左端或去掉右端的较大值dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);}}}returndp[0][n-1];}四、️ 题目对比总览题号题目难度核心算法关键点125验证回文串 Easy双指针过滤非字母数字409最长回文串构造 Easy贪心/哈希偶数全用奇数-1中间放1个680验证回文串 II Easy双指针不匹配时分两路试5最长回文子串 Medium中心扩展/DP奇偶两种中心647回文子串计数 Medium中心扩展/DP每个中心累计计数516最长回文子序列 MediumDP子序列≠子串dp转移不同五、⭐ 解法选择指南 常见坑选哪种算法✅ 优先选 中心扩展法代码短空间O(1) 适用于LC 5、LC 647 ✅ 需要记录所有子串状态时选 DP 适用于LC 647、LC 516子序列必须用DP ✅ 简单验证选 双指针 适用于LC 125、LC 680⚠️ 常见坑点总结// 坑1DP 填表顺序错误// ❌ 错误i 从小到大dp[i1][j-1] 还没算出来for(inti0;in;i)for(intji;jn;j)// ❌// ✅ 正确i 从大到小保证 dp[i1][...] 已经算好for(intin-1;i0;i--)for(intji;jn;j)// ✅// 坑2偶数长度中心扩展别忘了expand(s,i,i);// 奇数 ✅expand(s,i,i1);// 偶数 ✅ 别漏了这行// 坑3子串 vs 子序列 DP 定义不同// 子串dp[i][j] s[i..j] 是否回文boolean// 子序列dp[i][j] s[i..j] 最长回文子序列长度int// 坑4substring 截取区间s.substring(l1,r);// 中心扩展结束后 l 和 r 已经越界一步六、 刷题推荐顺序第1天LC 125 验证回文串掌握双指针基础第2天LC 409 最长回文串掌握贪心思路第3天LC 680 验证回文串II双指针进阶第4天LC 647 回文子串中心扩展法入门第5天LC 5 最长回文子串中心扩展 DP双解第6天LC 516最长回文子序列DP进阶回文串刷题路线学习建议先用中心扩展法刷通 LC 5 和 LC 647理解奇偶双中心的思想再用DP重新实现一遍对比两种写法的异同。LC 516 的子序列 DP 是单独的一类思路重点理解状态转移方程。
LeetCode 回文子串专题学习笔记（Java）
一、 回文串基础概念回文串正读和反读完全相同的字符串。a ✅ 单字符均是回文 aba ✅ 奇数长度回文中心是 b abba ✅ 偶数长度回文中心在两个 b 之间 abc ❌ 不是回文关键性质贯穿所有题目单个字符一定是回文串若s[i] s[j]且s[i1..j-1]是回文 →s[i..j]是回文回文串去掉首尾两个字符后仍是回文串二、 两大核心算法️ 算法一中心扩展法思路枚举每一个中心点向两边扩展只要两端字符相等就继续。⚠️ 注意中心点分两种情况奇数长度中心是某个字符如aba中心是b偶数长度中心是两个字符之间如abba中心在两个b之间/** * 中心扩展法通用模板 * 以 (left, right) 为中心向外扩展返回最长回文子串 */privateStringexpandAroundCenter(Strings,intleft,intright){while(left0rights.length()s.charAt(left)s.charAt(right)){left--;right;}// 循环结束时 left 和 right 已经越界所以截取 [left1, right-1]returns.substring(left1,right);}// 调用方式for(inti0;is.length();i){StringoddexpandAroundCenter(s,i,i);// 奇数长度以 i 为中心StringevenexpandAroundCenter(s,i,i1);// 偶数长度以 i,i1 为中心}时间复杂度O(n²) 空间复杂度O(1)️ 算法二动态规划DP思路用二维dp[i][j]表示s[i..j]是否为回文串。状态转移方程dp[i][j] true, 当 s[i] s[j] 且 (j-i2 或 dp[i1][j-1]true) dp[i][j] false, 当 s[i] ! s[j]初始化所有dp[i][i] true单字符是回文/** * 动态规划通用模板 */intns.length();boolean[][]dpnewboolean[n][n];// ⚠️ 重要必须按子串长度从小到大填表不能直接双重 i,j 循环for(intin-1;i0;i--){// i 从右往左for(intji;jn;j){// j 从左往右保证 j iif(s.charAt(i)s.charAt(j)){// 长度 2或者内部子串也是回文dp[i][j](j-i2)||dp[i1][j-1];}else{dp[i][j]false;}}}时间复杂度O(n²) 空间复杂度O(n²)三、 核心题目精讲✅ LC 125 — 验证回文串Easy题意只考虑字母和数字字符忽略大小写判断是否回文。考点双指针 字符过滤publicbooleanisPalindrome(Strings){intleft0,rights.length()-1;while(leftright){// 跳过非字母数字字符while(leftright!Character.isLetterOrDigit(s.charAt(left)))left;while(leftright!Character.isLetterOrDigit(s.charAt(right)))right--;// 忽略大小写比较if(Character.toLowerCase(s.charAt(left))!Character.toLowerCase(s.charAt(right))){returnfalse;}left;right--;}returntrue;}✅ LC 409 — 最长回文串Easy题意给定字符集合用这些字符能组成的最长回文串长度是多少核心思路偶数个的字符可以全部用上奇数个的字符只能用count - 1个凑成偶数最终可以在中间放一个奇数字符publicintlongestPalindrome(Strings){int[]freqnewint[128];for(charc:s.toCharArray())freq[c];intlength0;booleanhasOddfalse;for(intcount:freq){length(count/2)*2;// 取偶数部分if(count%21)hasOddtrue;}returnhasOdd?length1:length;// 有奇数字符可以放中间}✅ LC 680 — 验证回文串 IIEasy题意最多删除一个字符判断是否能构成回文串。核心思路双指针遇到不匹配时尝试跳过左或右字符验证剩余部分是否回文。publicbooleanvalidPalindrome(Strings){intleft0,rights.length()-1;while(leftright){if(s.charAt(left)!s.charAt(right)){// 两种跳法任意一种满足即可returnisPalin(s,left1,right)||isPalin(s,left,right-1);}left;right--;}returntrue;}// 辅助函数验证 s[l..r] 是否回文privatebooleanisPalin(Strings,intl,intr){while(lr){if(s.charAt(l)!s.charAt(r--))returnfalse;}returntrue;}✅ LC 5 — 最长回文子串Medium题意找出字符串中最长的回文子串。解法1中心扩展法推荐publicStringlongestPalindrome(Strings){Stringresult;for(inti0;is.length();i){Stringoddexpand(s,i,i);// 奇数中心Stringevenexpand(s,i,i1);// 偶数中心if(odd.length()result.length())resultodd;if(even.length()result.length())resulteven;}returnresult;}privateStringexpand(Strings,intl,intr){while(l0rs.length()s.charAt(l)s.charAt(r)){l--;r;}returns.substring(l1,r);}解法2动态规划publicStringlongestPalindrome(Strings){intns.length(),start0,maxLen1;boolean[][]dpnewboolean[n][n];for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)(j-i2||dp[i1][j-1])){dp[i][j]true;if(j-i1maxLen){maxLenj-i1;starti;}}}}returns.substring(start,startmaxLen);}✅ LC 647 — 回文子串Medium题意计算字符串中共有多少个回文子串。解法1中心扩展法推荐publicintcountSubstrings(Strings){intcount0;for(inti0;is.length();i){countexpandCount(s,i,i);// 奇数countexpandCount(s,i,i1);// 偶数}returncount;}privateintexpandCount(Strings,intl,intr){intcount0;while(l0rs.length()s.charAt(l)s.charAt(r)){count;l--;r;}returncount;}解法2动态规划publicintcountSubstrings(Strings){intns.length(),count0;boolean[][]dpnewboolean[n][n];for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)(j-i2||dp[i1][j-1])){dp[i][j]true;count;}}}returncount;}✅ LC 516 — 最长回文子序列Medium题意找最长的回文子序列长度子序列不要求连续。⚠️ 注意区别子串连续vs子序列不连续DP 定义dp[i][j]s[i..j]中最长回文子序列的长度publicintlongestPalindromeSubseq(Strings){intns.length();int[][]dpnewint[n][n];// 初始化每个单字符是长度为1的回文子序列for(inti0;in;i)dp[i][i]1;for(intin-1;i0;i--){for(intji1;jn;j){if(s.charAt(i)s.charAt(j)){dp[i][j]dp[i1][j-1]2;// 两端字符相同加入子序列}else{// 两端不同取去掉左端或去掉右端的较大值dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);}}}returndp[0][n-1];}四、️ 题目对比总览题号题目难度核心算法关键点125验证回文串 Easy双指针过滤非字母数字409最长回文串构造 Easy贪心/哈希偶数全用奇数-1中间放1个680验证回文串 II Easy双指针不匹配时分两路试5最长回文子串 Medium中心扩展/DP奇偶两种中心647回文子串计数 Medium中心扩展/DP每个中心累计计数516最长回文子序列 MediumDP子序列≠子串dp转移不同五、⭐ 解法选择指南 常见坑选哪种算法✅ 优先选 中心扩展法代码短空间O(1) 适用于LC 5、LC 647 ✅ 需要记录所有子串状态时选 DP 适用于LC 647、LC 516子序列必须用DP ✅ 简单验证选 双指针 适用于LC 125、LC 680⚠️ 常见坑点总结// 坑1DP 填表顺序错误// ❌ 错误i 从小到大dp[i1][j-1] 还没算出来for(inti0;in;i)for(intji;jn;j)// ❌// ✅ 正确i 从大到小保证 dp[i1][...] 已经算好for(intin-1;i0;i--)for(intji;jn;j)// ✅// 坑2偶数长度中心扩展别忘了expand(s,i,i);// 奇数 ✅expand(s,i,i1);// 偶数 ✅ 别漏了这行// 坑3子串 vs 子序列 DP 定义不同// 子串dp[i][j] s[i..j] 是否回文boolean// 子序列dp[i][j] s[i..j] 最长回文子序列长度int// 坑4substring 截取区间s.substring(l1,r);// 中心扩展结束后 l 和 r 已经越界一步六、 刷题推荐顺序第1天LC 125 验证回文串掌握双指针基础第2天LC 409 最长回文串掌握贪心思路第3天LC 680 验证回文串II双指针进阶第4天LC 647 回文子串中心扩展法入门第5天LC 5 最长回文子串中心扩展 DP双解第6天LC 516最长回文子序列DP进阶回文串刷题路线学习建议先用中心扩展法刷通 LC 5 和 LC 647理解奇偶双中心的思想再用DP重新实现一遍对比两种写法的异同。LC 516 的子序列 DP 是单独的一类思路重点理解状态转移方程。
