【马拉车算法/动态规划】最长回文字串-Toy模板网

这篇具有很好参考价值的文章主要介绍了【马拉车算法/动态规划】最长回文字串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.问题描述

【马拉车算法/动态规划】最长回文字串,labuladong的算法小抄笔记,算法,动态规划,Manacher
常用有3种算法：中心扩展法、动态规划和Manacher算法

2.中心扩展法（O(N^2)）

解释：
从中心向外扩展。
分为两种情况：第一种当回文串长度为奇数的情况；第二种当回文串长度为偶数的情况。
左右同时向外扩展，当左右不相同时停止扩展，记录最长回文串长度及起始位置。

    public String longestPalindrome(String str) {
        if (Objects.isNull(str) || str.isEmpty()) {
            return "";
        }
        int maxStart = 0;
        int maxLength = 1;
        for (int i = 0; i < str.length(); i++) {
            for (int k = 0; k < 2; ++k) {
                int leftIndex = i - k; // k = 0表示偶数长度，k = 1表示奇数长度
                int rightIndex = i + 1;
                while (leftIndex >= 0
                        && rightIndex < str.length()
                        && str.charAt(leftIndex) == str.charAt(rightIndex)) {
                    leftIndex--;
                    rightIndex++;
                }
                if (maxLength < rightIndex - leftIndex - 1) { // 当前length = (rightIndex - 1) - (leftIndex + 1) + 1
                    maxLength = rightIndex - leftIndex - 1;
                    maxStart = leftIndex + 1;
                }
            }
        }

        return str.substring(maxStart, maxStart + maxLength);
    }

3.动态规划（O(N^2)）

首先初始化一个维度为length的二维单位阵（对角全为1，其余为0）；判断是否有长度为2的回文串，如有则起始和终止索引在矩阵中对应的位置为1。
递归的思路为当起始点i到终止点j为回文串，则起始点i+1到终止点j-1也是回文串。因此从长度为3开始进行判断，当发现回文串时，修改矩阵对应位置值为1，并进行长度和起始位置的记录。

    public String longestPalindromeDP(String str) {
        if (Objects.isNull(str) || str.isEmpty()) {
            return "";
        }
        int maxStart = 0;
        int maxLength = 1;
        int[][] dp = new int[str.length()][str.length()];
        for (int i = 0; i < str.length(); i++) {
            dp[i][i] = 1;
            if (i + 1 < str.length() && str.charAt(i) == str.charAt(i + 1)) {
                dp[i][i + 1] = 1;
                maxStart = i;
                maxLength = 2;
            }
        }

        for (int L = 3; L <= str.length(); ++L) {
            for (int i = 0; i + L - 1 < str.length(); ++i) {
                int j = i + L - 1;
                if (str.charAt(i) == str.charAt(j) && dp[i + 1][j - 1] == 1) {
                    dp[i][j] = 1;
                    maxStart = i;
                    maxLength = L;
                }
            }
        }

        return str.substring(maxStart, maxStart + maxLength);
    }