【区间dp-回文-1】最长回文子串(或长度）

同 leet 5. 最长回文子串

描述

给定一个字符串str, 返回str中最长回文子串的长度

[举例]

str=“123”。其中的最长回文子串“1”或者“2”或者“3”，所以返回1。

str=“abc1234321ab”。其中的最长回文子串“1234321”，所以返回7。

[要求]

如果str的长度为N，解决原问题的时间复杂度都达到O(N).

输入描述：

输入为一个字符串str

输出描述：

输出一个整数表示最长回文子串的长度

示例1

输入：

123

输出：

1

示例2

输入：

abc1234321ab

输出：

7

备注：

设N表示输入字符串的长度保证输入字符中只含有小写字母及数字1⩽N⩽5∗1051⩽N⩽5∗105

是manacher算法的经典应用题。本次题目不用中心扩展法，也不用manacher算法，用动态规划，时间复杂度是O（n*n）。回文字符串用区间动态规划算是模板算法了，后面还有很多题目用到它，必须要掌握。

构建关键dp二维数组，boolean[][] dp=new int[n][n] , dp[i][j]表示字符串的left=i，right=j的字符串是否是回文。

很明显动态规划公式分以下几种情况. 外部r从【0->n-1】迭代，内部 l 从 【r->0】迭代

dp[i][j]= true , i==j

dp[i][j]=true, i+1=j并且s[i]=s[j]

dp[i][j]=true, dp[i+1][j-1]=true&&s[i]=s[j].

所以总结可以用以下算法来获取dp[i][j]

public boolean[][] palindrome(String s) {

        int n=s.length();
        boolean[][] dp = new boolean[n][n];
        String  ans=s.substring(0,1);
        for (int r = 0; r < s.length(); r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r || s.charAt(l) == s.charAt(r) && (l + 1 == r || dp[l + 1][r - 1] == true)) {
                    dp[l][r] = true;
                }
            }
        }
        return dp;
    }

所以最长回文子串出现的时候是dp[l][r]=true而且r-l+1是最长的时候。

算法可以写成如下：

求最长回文子串

  public String longestPalindrome(String s) {
        
            int n=s.length();
            int maxLen=1;
            boolean[][] dp = new boolean[n][n];
            String  ans=s.substring(0,1);
            for (int r = 0; r < s.length(); r++) {
                for (int l = r; l >= 0; l--) {
                    if (l == r || s.charAt(l) == s.charAt(r) && (l + 1 == r || dp[l + 1][r - 1] == true)) {
                        dp[l][r] = true;
                        if(maxLen<r-l+1){
                            maxLen=r-l+1;
                            ans=s.substring(l,r+1);
                        }
                    }
                }
            }
            return ans;
        }

求最长回文子串长度

  public int longestPalindromeLength(String s) {
            int n=s.length();
            int maxLen=1;
            boolean[][] dp = new boolean[n][n];
            for (int r = 0; r < s.length(); r++) {
                for (int l = r; l >= 0; l--) {
                    if (l == r || s.charAt(l) == s.charAt(r) && (l + 1 == r || dp[l + 1][r - 1] == true)) {
                        dp[l][r] = true;
                        if(maxLen<r-l+1) maxLen=r-l+1;
                    }
                }
            }
            return maxLen;
        }