java 最长回文字符串

1. 输入描述

输入一个字符串（字符串的长度不超过2500）

2. 输出描述

返回有效密码串的最大长度

3. 解法思路

针对最长的回文字符串，在给定的一个字符串内，无疑有两种形式，AA 或者 ABA形式。 注意边界问题

最长的回文 最前和最后去掉一位也是回文。利用此思路来求解。 我们用一个二维矩阵 a[n][n] 来代替字符串. 其中行数代表当前长度 列数代表字符串的位数 二维数组的值代表字符串的回文串长度。

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str = in.next();
        int n = str.length();
        int[][] a = new int[n][n];
        for(int i=0;i<2;i++)
            for(int j=0;j<n;j++){
                if (i==0)
                    a[i][j]=1;
                else{
                    if(j>=1){
                        if(str.charAt(j)==str.charAt(j-1))
                            a[i][j] = i+1;
                    }else{
                        a[i][j]=a[i-1][j];
                    }
                }
            }
        
        for(int i=2;i<n;i++){
            for(int j=0;j<n;j++){
                if(i%2==0){
                    if((j-i/2)>=0&&(j+i/2)<n&&a[i-2][j]==(i-2+1)){
                        if(str.charAt(j-i/2)==(str.charAt(j+i/2)))
                            a[i][j] = i+1;
                        else
                            a[i][j] = Math.max(a[i-2][j],a[i-1][j]);
                    }
                }else{
                    if((j-i/2-1)>=0&&(j+i/2)<n&&a[i-2][j]==(i-2+1)){
                        if(str.charAt(j-i/2-1)==(str.charAt(j+i/2)))
                            a[i][j] = i+1;
                        else
                            a[i][j] = Math.max(a[i-2][j],a[i-1][j]);
                    }
                }
            }
        }
        int longmax=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if (a[i][j]>longmax)
                    longmax = a[i][j];
            }
        System.out.println(longmax);
    }
}