[数据结构与算法]最长回文子串

最长回文子串

最长回文子串，比较常考的一道算法题，主要用来练习动态规划
可以直接复制下面的代码去自己的IDE

package com.wy.string;

/**
 * 最长回文子串，三种解法 1：动态规划、2：中心扩散、3：Manacher , 参考 https://blog.nowcoder.net/n/99462149a22d479ba9a3d5c8e7fd0247
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        String str = "123abcba?";
        System.out.println(getLongestPalindrome1(str));
    }
    //1.动态规划法 时间复杂度O(n^2) 空间复杂度O(n^2)
    // (d[i][j]为bool类型)，先列公式,画图表格，分别判断i和j，从0开始还是从n开始，其实一画出图来，用公式在图上看一看，看d[i][j] = d[*][*]的依赖关系，就一目了然了
    //dp[i][j] = dp[i+1]dp[j-1]
    public static int getLongestPalindrome1(String str){
        if(str.length() == 1) return 0;
        char[] chars = str.toCharArray();
        int[][] dp = new int[str.length()][str.length()];
        int maxlength = 0;
        for (int i = str.length() - 1; i >= 0; i--) {
            for (int j = i; j < str.length(); j++) {
                if(chars[i] == chars[j]){
                    if(j - i <= 2){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] == 1)
                    maxlength = Math.max(maxlength, j - i + 1);
            }
        }
        return maxlength;
    }

    //2.中心扩散法 时间复杂度O(n^2) 空间复杂度O(n^2)
    //将每个字符串当做回文的中心位置，则有中心位置为b，abba（偶数），或中心位置为b，aba(基数) 两种情况
    public int getLongestPalindrome2(String A, int n) {
        if(n < 2) {
            return n;
        }
        // 最大长度
        int res = 0;
        // 每个字符都可以尝试作为中心点
        for(int i = 0; i < n; i++) {
            // 两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
            // 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
            int len = Math.max(helper(A, i, i), helper(A, i, i + 1));
            // 更新最大长度
            res = Math.max(res, len);
        }
        return res;
    }

    public int helper(String A, int left, int right) {
        // 从left到right开始向两边扩散、比较
        while(left >= 0 && right < A.length()) {
            // 如果相等则继续扩散比较
            if(A.charAt(left) == A.charAt(right)) {
                left--;
                right++;
                continue;
            }
            // 如果不相等则剪枝，不用再继续扩散比较
            break;
        }
        // "+1"是因为通过下标计算子串长度
        // "-2"是因为上边的while循环是当索引为left和right不想等才退出循环的
        // 因此此时的left和right是不满足的，需要舍弃
        return right - left + 1 - 2;

    }

    //3.Manacher 不常规，知道有这种方法即可，看链接吧

}

参考链接