最长回文子串

有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步, 认准 https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java 面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。https://store.amazingmemo.com/chapterDetail/1685324709017001`

最长回文子串问题

在字符串处理中，最长回文子串 问题是一个经典问题，它要求找到一个给定字符串中最长的子串，这个子串无论从前向后读还是从后向前读都是相同的。

解决方法

有几种不同的方法可以解决这个问题，包括动态规划、中心扩展算法和 Manacher 算法。

动态规划

动态规划的方法是创建一个二维数组 dp[i][j]，其中 i 和 j 分别表示字符串中的开始和结束索引，dp[i][j] 表示从 i 到 j 的子串是否是回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String longestPalindromeDP(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    String res = "";

    for (int len = 0; len < n; len++) {
        for (int start = 0; start + len < n; start++) {
            int end = start + len;
            dp[start][end] = (len == 0 || len == 1 || dp[start + 1][end - 1]) && s.charAt(start) == s.charAt(end);
            if (dp[start][end] && len + 1 > res.length()) {
                res = s.substring(start, end + 1);
            }
        }
    }
    return res;
}

中心扩展算法

中心扩展算法的思想是，对于每个可能的回文中心（字符或两个字符之间的空隙），向两边扩展，直到不能形成更长的回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String longestPalindromeExpandAroundCenter(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

Manacher 算法

Manacher 算法是解决最长回文子串问题的最优算法，时间复杂度为 O(n)。它通过在字符之间插入分隔符（通常是一个不会在输入字符串中出现的字符，如 #），将奇数长度和偶数长度的回文统一处理。

1
2
3
4
5
6
7
public String longestPalindromeManacher(String s) {
    // 此处省略 Manacher 算法的实现细节
    // 通常包括预处理字符串，在每个字符之间插入分隔符
    // 然后使用 Manacher 算法的核心逻辑来找到最长回文子串
    // 最后从处理后的字符串中提取出原始字符串的最长回文子串
    return "";
}

总结

以上就是解决最长回文子串问题的三种常见方法。动态规划的时间复杂度为 O(n^2)，空间复杂度也为 O(n^2)；中心扩展算法的时间复杂度为 O(n^2)，但空间复杂度降低到了 O(1)；Manacher 算法提供了最优的时间复杂度 O(n)，但实现起来相对复杂。在实际应用中，可以根据具体情况选择合适的算法。