java - 最长回文程序

Question

我正在经历这个longest palindrome program :

   public static String longestPalindrome(String s) {
        if(s==null || s.length()<=1)
            return s;

        int len = s.length();
        int maxLen = 1;
        boolean [][] dp = new boolean[len][len];

        String longest = null;
        for(int k=0; k<s.length(); k++){
            for(int i=0; i<len-k; i++){
                int j = i+k;
                if(s.charAt(i)==s.charAt(j) && (j-i<=2||dp[i+1][j-1])){
                    dp[i][j]=true;

                    if(j-i+1>maxLen){
                       maxLen = j-i+1; 
                       longest = s.substring(i, j+1);
                    }
                }
            }
        }

        return longest;
    }

我在我的 eclipse 中多次以 Debug模式运行这个程序，但我不清楚这个程序是如何获得最长回文值的。

boolean 数组如何使用，变量j如何使用是用的，主要是这个条件有什么用j-i<=2||dp[i+1][j-1]

链接说空间复杂度是O(n^2) , 程序的哪一部分表明了这个空间复杂度。

Answer 1

这是一种动态程序方法。从一个字母串(默认情况下为回文)开始，逐渐增加字符串中的字母数。

为此他们使用二维数组，

    /*
 *      B  A  N  A  N  A
 *     ------------------
 *  B | T  F  F  F  F  F
 *  A |    T  F  T  F  T
 *  N |       T  F  T  F
 *  A |          T  F  T 
 *  N |             T  F
 *  A |                T
 * */

因此空间复杂度为 n^2。

对于任何 [i][j] 单元格，您需要检查 [i+1][j-1] 单元格，以确定添加此字母之前的子字符串是否为回文。

下面的链接有一个非常清晰的视频，它使用了类似的方法。
http://www.ideserve.co.in/learn/longest-palindromic-substring