【算法题】最长回文子串

首先我们要清楚回文串的特性，就是对称的，那么可以这样想，如果一个字符串如果他是回文的，那么分别在她前后各加一个相等字符，那么加了后的新的字符串是不是也是回文的。所以这道题在判断是否回文时是在前一个串是回文的前提下的。

所以这道题就是通过在她的子串是回文的前提下来判断前后各加一个字符后是否回文，因此我们可以用动态规划来写，定义一个boolean类型的二维dp数组来判断该子串是否回文，如果是则为true，否则为false。然后在得到新的回文子串后就对长度进行更新。

代码如下

class Solution {public String longestPalindrome(String s) {int n=s.length();//dp[a][b]表示s.substring(a,b+1)是否回文boolean [][]dp=new boolean[n][n];for(int i=0;i<n;i++){dp[i][i]=true;}int left=0;//回文串的起点int length=1;//回文串的最大长度for(int r=1;r<n;r++){for(int l=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>length){length=r-l+1;left=l;     }} }}return s.substring(left,left+length);  }
}