[编程题]最长回文子串

最长回文子串

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。

测试样例：

"abc1234321ab",12

返回：7

方法一：

常规方法，直接遍历找出最大回文串。

import java.util.*;

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        int max = 1;
        for(int j = 2; j <= n; j++){
            for(int i = 0; i < j && j - i > max; i++){
                String t = A.substring(i, j);
                if(isHuiWen(t))
                    max = j - i;
            }
        }
        return max;
    }

    public boolean isHuiWen(String str){
        return str.equals(new StringBuffer(str).reverse().toString());
    }
}

方法二：

动态规划：

1. 用d[i][j]表示从第i到第j个元素是否为回文串，d[i][j]的初始值为false;
2. 若d[i+1][j-1]==true AND A[i]==A[j]，则d[i][j]是回文串；
3. 初始情况是d[i][i]=true, i=1,2,3...n-1;
4. 边界考虑：A==null || A为空，返回0。若A.length()==1，返回maxLen的初始值1。

import java.util.*;

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        if(A == null || A.length() == 0)
            return 0;

        char[] a = A.toCharArray();
        boolean[][] d = new boolean[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < i; j++)
                d[j][i] = false;

        int maxLen = 1;
        for(int j = 1; j < n; j++){
            d[j][j] = true;
            for(int i = 0; i < j; i++){
                if(j - i == 1 && a[i] == a[j]){
                    d[i][j] = true;
                } else if(d[i + 1][j - 1] && a[i] == a[j]){
                    d[i][j] = true;
                }

                if(d[i][j])
                    maxLen = Math.max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
}