题解 | #最长回文子串#

描述

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

示例1

输入：
"abc1234321ab",12
返回值：
7

题解

动态规划思路：

dp[n][m]代表n-m这一段子字符串是否为回文类型，为boolean类型的二维数组。

• n = m 时，dp[n][m] = true
• 双层循环遍历所有子串的思路：因为要利用dp[i+1][j-1]来进行递推dp[i][j], 所以应该是子串的末尾固定，子串的起始位置向前进行遍历，这样就能确保最小回文子串的dp[][]结果能被充分利用。

  动态规划就是要划分为子问题，向外逐步递推出总结果。

  JAVA代码如下：

  import java.util.*;
  public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        boolean[][] dp = new boolean[n][n];
        int max = 1;
        for(int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        char[] string = A.toCharArray();
        for(int i = 1; i < n; i++) {  // i作为末尾
            for(int j = i - 1; j >= 0; j--) {  // j作为起始
                if(i - j == 1) {
                    dp[j][i] = (string[i] == string[j]);
                }
                else {
                    dp[j][i] = dp[j + 1][i - 1] && (string[j] == string[i]);
                }
                if(dp[j][i] && max < i - j + 1) {
                    max = i - j + 1;
                }
            }
        }
        return max;
    }
  }