5. 最长回文子串 - 力扣（LeetCode）

这道题目要注意，有两种类型的回文子串

（1）aba型：比如ccacc

（2）aabb型：比如ccaacc

两种解法解决这道题目：动态规划法和中心扩散法(双指针法)

第一种解法：中心扩散法

help函数的功能是求出以l,r为中心向两边扩散，最长的回文字符串（返回值是这个最长的回文字符串，而不是最长回文字符串的长度），help函数里面主要是一个while函数，跳出while函数说明左指针和右指针指向的字符不相等了，求出此时的字符串

class Solution
{public String longestPalindrome(String s){//从中心向两端扩散的双指针技巧//回文串的长度可能是奇数，也可能是偶数//有几个中心字符？如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符String result="";for(int i=0;iresult.length())//如果求出来的字符串长度更长{result=s1;}//以 s[i] 和 s[i+1] 为中心的最长回文子串String s2 = help(s, i, i + 1);  if(s2.length()>result.length()){result=s2;}}return result;}// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串// 如果回文串的长度是奇数，只有1个中心字符，输入相同的l和r即可//如果回文串的的长度是偶数，有两个中心字符，输入相邻的l和rpublic String help(String s, int l, int r) {// 防止越界while (l >= 0 && r < s.length()&& s.charAt(l) == s.charAt(r)) {// 双指针，向两边展开l--;r++;}//跳出循环的时候,s.charAt(l)!=s.charAt(r),由于substring方法是左闭右开，所以是返回s.substring(l + 1, r);// 返回以 s[l] 和 s[r] 为中心的最长回文串return s.substring(l + 1, r);}
}

第二种解法：动态规划

动态规划三部曲：

(1)确定dp[i]或者dp[i][j]的含义

(2)确定递推关系(状态转移方程)

(3)确定递推顺序（也就是从左往右递推还是从右往左递推，从左上角开始递推还是从右下角开始递推）

注意回文子串的性质，一个回文子串去掉第一个字符和最后一个字符，剩下的字符串依然是回文字符串，s[i]~s[j]如果是回文子串，当s[i-1]==s[j+1]的时候，s[i-1]~s[j+1]也是回文子串

反过来：一个子串是不是回文子串，取决于

（1）两边的字符是不是相等

（2）中间的子串是不是回文子串

 当子串长度小于4(那子串长度只能等于2或者3)，当两边字符相等时,那子串一定是回文子串

只有下面两种情况：

(1)确定dp[i]含义：dp[i][j]表示s[i]~s[j]这个子串是不是回文子串，比如这里dp[1][3]=false

（2）状态转移方程：

根据dp[i+1][j-1] 推出dp[i][j]

（3)递推顺序，从第一列到最后一列，每一列从第一行到最后一行，所以是：

for(int j=1;j

{

     for(int i=0;i

    {

    }

}

由于j一定是大于等于i的，所以只需要填满这张图的上三角部分即可

代码实现如下：

class Solution 
{public String longestPalindrome(String s){int n=s.length();boolean[][] dp=new boolean[n][n];for(int i=0;imax_len){result=s.substring(i,j+1);max_len=j-i+1;}}}if(max_len==1)   return   s.substring(0,1);//最终如果max_len=1,说明abcde这种，返回第一个字符即可return  result;}
}