NC17 最长回文子串

二刷 dp改进了

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int[][] dp = new int[n][n];

        for(int i=0;i<n;i++){
            dp[i][i] = 1;
        }
        int max = 0;
        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){
                if(A.charAt(i) == A.charAt(j)){
                    if(j-i == 1) dp[i][j] = 2;
                    else{
                        //这里不要忘了判断dp[i+1][j-1]>0是否为回文串
                        if(dp[i+1][j-1]>0) dp[i][j] = dp[i+1][j-1] + 2;
                        else dp[i][j] = 0;
                        max = Math.max(dp[i][j],max);
                    }
                }
                else dp[i][j] = 0;
            }
        }
        return max;
    }
}

1.动态规划

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // 特殊用例判断
        if (n < 2) {
            return n;
        }
        int maxLen = 1;
        // 初始化
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }
        // 更新 i j 这个字符串回文的左右两边， 如果i==j 且 ij 距离小于等于2 那么直接判断
        // 是回文，否则就需要根据 dp[i+1][j-1] 来判断 
        // 如果dp为1  就代表这个字符串 从 i到j 闭包 的位置 是回文。
        for(int j=1; j<n; j++){
            for(int i=0; i<j; i++){
                if(A.charAt(i) != A.charAt(j)){
                    dp[i][j] = 0;
                }
                else{
                    if(j-i<3){
                        dp[i][j] = 1;
                    }
                    else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==1 && j-i+1> maxLen){
                    maxLen = j-i+1;
                }
            }
        }
        return maxLen;
    }
}

2.中心扩散
我最开始的想法。 但是没写 。 需要注意 不一定是奇数回文 需要判断回文是奇偶。

3. 马拉车
   https://www.bilibili.com/video/BV1Us411i7fu?p=2
   https://www.bilibili.com/video/BV1rE411x78x