LeetCode 005：最长回文子串

一、题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

样例：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

二、解题思路 

动态规划：设s[i][j]为从i到j的字符串。当c[i]和c[j]不相等时，s[i][j]一定不是回文串。当c[i]和c[j]相等时，其是否是回文串的性质和s[i+1][j-1]一样。初态为长度为1，一定是回文串。

Java代码：

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len < 2) {
            return s;
        }
        int maxlen=1;
        int begin=0;
        //dp[i][j]表示s[i..j]是否是回文串
        boolean[][]dp=new boolean[len][len];
        //初始化：所有长度为1的子串都是回文串
        for(int i=0;i
            dp[i][i]=true;                               
        }
        //将字符串转换为字符数组
        char[] chararray=s.toCharArray();
        //递推开始
        //先枚举子串长度
        for(int l=2;l<=len;l++){
            //枚举左边界
            for(int i=0;i
                //因为j-i+1=l，得到
                int j=l+i-1;
                //若右边界越界，退出循环
                if(j>=len){
                    break;
                }
                if(chararray[i]!=chararray[j]){
                    dp[i][j]=false;
                }else{
                    if(j-i<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxlen){
                    maxlen=j-i+1;
                    begin=i;
                }
 
            }
        }
        return s.substring(begin,begin+maxlen);
 
    }
}