LeetCode热题100--5. 最长回文子串--中等

题目

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

题解

classSolution{publicStringlongestPalindrome(Strings){if(s==null||s.length()<2){returns;}intstrLen=s.length();intmaxStart=0;//最长回文串的起点intmaxEnd=0;//最长回文串的终点intmaxLen=1;//最长回文串的长度boolean[][]dp=newboolean[strLen][strLen];for(intr=1;r<strLen;r++){for(intl=0;l<r;l++){if(s.charAt(l)==s.charAt(r)&&(r-l<=2||dp[l+1][r-1])){dp[l][r]=true;if(r-l+1>maxLen){maxLen=r-l+1;maxStart=l;maxEnd=r;}}}}returns.substring(maxStart,maxEnd+1);}}

解析

出自：中心扩散法和动态规划

classSolution{publicStringlongestPalindrome(Strings){// 如果字符串为空，或长度小于2（即0或1），直接返回原字符串（单个字符本身就是回文）if(s==null||s.length()<2){returns;}// 获取字符串的总长度intstrLen=s.length();// 记录最长回文子串的起始索引（包含）intmaxStart=0;// 记录最长回文子串的结束索引（包含）intmaxEnd=0;// 记录当前找到的最长回文子串的长度，初始为1（至少一个字符）intmaxLen=1;// 创建二维布尔数组 dp，dp[l][r] 表示子串 s[l...r] 是否为回文boolean[][]dp=newboolean[strLen][strLen];// 外层循环：遍历右边界 r，从1开始（因为长度为1的子串已是回文，无需处理）for(intr=1;r<strLen;r++){// 内层循环：遍历左边界 l，从0到r-1for(intl=0;l<r;l++){// 判断 s[l] 和 s[r] 是否相等，并且：// - 如果子串长度 <= 3（即 r - l <= 2，如 "aa" 或 "aba"），只要两端相等就是回文；// - 或者更长的子串，需依赖内部子串 s[l+1...r-1] 是否为回文（即 dp[l+1][r-1] 为 true）if(s.charAt(l)==s.charAt(r)&&(r-l<=2||dp[l+1][r-1])){// 标记 s[l...r] 为回文dp[l][r]=true;// 如果当前回文子串长度大于已记录的最大长度，则更新最大长度和起止位置if(r-l+1>maxLen){maxLen=r-l+1;// 更新最大长度maxStart=l;// 更新起始索引maxEnd=r;// 更新结束索引}}// 注意：如果 s[l] != s[r]，dp[l][r] 默认为 false（无需显式赋值）}}// 使用 substring 提取最长回文子串（注意：substring 的 end 是 exclusive，所以 +1）returns.substring(maxStart,maxEnd+1);}}