LeetCode 5：最长回文子串（Longest Palindromic Substring）—— 题解

LeetCode 5最长回文子串Longest Palindromic Substring题解 题目链接 https://leetcode.cn/problems/longest-palindromic-substring/ 题目描述给你一个字符串s找出其中最长的连续回文子串。若存在多个长度相同的最长回文子串返回任意一个即可。示例 1输入s “babad”输出“bab”解释“aba” 同样是符合题意的答案。示例 2输入s “cbbd”输出“bb”题目约束1 s.length 1000字符串仅由数字和英文字母组成 题目核心考点经典区间动态规划区间DP题型字符串子串问题、回文判定进阶应用面试高频算法原题重点考察DP状态定义、遍历顺序逻辑 解题核心思路DP解法暴力枚举所有子串再判断回文的方式时间复杂度为 O(n³)会超时。因此使用动态规划复用已计算的子问题结果将时间复杂度优化至 O(n²)。一、状态定义定义二维DP数组dp[i][j] 表示字符串区间 s[i...j] 是否为回文子串true是回文子串false不是回文子串二、状态转移方程核心回文子串的核心特性两端字符相等且中间包裹的子串也是回文。if (s[i] s[j]) { // 情况1单个字符 / 两个相邻相同字符一定是回文 if (j - i 1) { dp[i][j] true; } // 情况2区间长度大于2依赖内部子串的结果 else { dp[i][j] dp[i 1][j - 1]; } }简单总结首尾字符相同且内部子串是回文则当前区间是回文。三、关键遍历顺序易错重点dp[i][j]的状态依赖于dp[i1][j-1]因此遍历顺序固定i左边界从后往前遍历j右边界从前往后遍历该顺序保证计算大区间时内部小区间的子问题已经算完。for (int i len - 1; i 0; i--) for (int j i; j len; j)✅ 完整AC代码修缮你的原代码classSolution{publicStringlongestPalindrome(Strings){// 初始最长长度为1答案初始化为第一个字符修复原代码空串BUGintmaxLen1;Stringanss.substring(0,1);intlens.length();char[]charArrs.toCharArray();boolean[][]dpnewboolean[len][len];// 左边界倒序遍历for(intilen-1;i0;i--){// 右边界正序遍历for(intji;jlen;j){if(charArr[i]charArr[j]){// 长度1、2直接回文if(j-i1){dp[i][j]true;}else{// 长度大于2依赖内部dp[i][j]dp[i1][j-1];}// 更新最长回文子串if(dp[i][j](j-i1)maxLen){maxLenj-i1;anss.substring(i,j1);}}}}returnans;}}⏱️ 复杂度分析指标复杂度说明时间复杂度O(n²)两层循环枚举所有区间空间复杂度O(n²)二维dp数组开销 核心一句话总结区间DP首尾相等且内部子串回文 → 当前区间回文逆序遍历左边界保证子问题先解。 面试高频追问必背1. 为什么 i 必须倒序遍历dp[i][j]依赖dp[i1][j-1]也就是当前行依赖下一行。只有 i 从后往前算i1的结果才已经提前算好了。2. 为什么要单独判断j - i 1当子串长度为 1、2 时i1 j-1没有内部子区间不能走转移方程需要手动初始化基准回文。3. 可以优化空间吗可以。中心扩展法空间 O(1)时间同样 O(n²)是面试最优解。需要我把中心扩展法的完整题解代码也直接贴给你吗