解题思路

动态规划

 public String longestPalindrome(String s) {
        int length = s.length();
        String res = "";
        boolean[][] dp = new boolean[length][length];
        for(int i=length-1;i>=0;i--){
            for(int j=i;j<length;j++){
                //计算dp
                dp[i][j]=s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1]);
                //计算最大回文
                if(dp[i][j]&&j-i+1>res.length())
                    res = s.substring(i, j+1);
            }
        }  
        return res;
    }

中心扩展法

public String longestPalindrome(String s) {
        if(s.equals(""))
            return "";
        int l = 0;        //记录左边的索引
        int r = 0;      //记录右边的索引
        int maxLength = 0;
        int n = s.length();
        for(int i =0;i<n;i++){
            //对于aba类的情况
            for(int step=0;step<Math.min(i+1,n-i);step++){ //step表示扩展的长度
                if(s.charAt(i-step)!=s.charAt(i+step))
                    break;        //不对称则退出
                if(2*step+1>maxLength){    //记录最大值
                    maxLength = 2*step+1;
                    l = i-step;
                    r = i+step;
                }
            }
            //对于abba类问题
            if(i+1<n&&s.charAt(i)==s.charAt(i+1)){
                //注意下标
                for(int step=0;step<Math.min(i+1,n-i-1);step++){
                    if(s.charAt(i-step)!=s.charAt(i+step+1))
                        break;
                    if(2*step+2>maxLength){   //长度值是不同的
                        maxLength = 2*step+2;
                        l = i-step;
                        r = i+step+1;
                    }
                }
            }
        }
        return s.substring(l,r+1);        //返回最大的子串
    }