递归实现最长回文子串存在误判Bug，寻求修复方案

问题根源 #

你代码的核心错误在于：当字符串两端字符相等时，错误地将中间子串的最长回文长度加2作为当前结果。但这个逻辑只在「中间整个子串本身是回文」时才成立，而你写的判断条件if (pal != 1 || str.length() <= 3)完全无法验证这一点，导致遇到两端字符相同但中间并非整体回文的情况时，会输出错误结果。

举个实际例子：输入字符串"abacaa"，两端都是a，中间子串是"baca"。你的代码会算出中间子串的最长回文长度是3（对应"aca"），然后触发return 2+3=5，但实际上整个"abacaa"并不是回文，它的最长回文子串长度只有3，这就是bug的直观表现。

修正后的代码 #

要解决这个问题，我们需要在两端字符相等时，先判断中间子串的最长回文长度是否等于中间子串的自身长度——如果相等，说明中间子串是完整的回文，此时才能将两端字符加进去组成更长的回文；否则，还是需要递归取去掉左端或右端后的最大值。

public static int palindrome(String str) {
    str = str.toLowerCase();
    int len = str.length();
    if (len == 0)
        return 0;
    if (len == 1)
        return 1;

    if (str.charAt(0) == str.charAt(len - 1)) {
        int midLen = len - 2;
        int pal = palindrome(str.substring(1, len - 1));
        // 只有中间子串本身是回文时，才能和两端字符组成更长回文
        if (pal == midLen) {
            return 2 + pal;
        }
    }
    // 否则取两种截断方式的最大值
    return Math.max(palindrome(str.substring(0, len - 1)), palindrome(str.substring(1)));
}

补充说明 #

这个递归解法的时间复杂度是O(2^n)，对于长度超过15的字符串就会明显变慢。如果需要处理更长的字符串，推荐使用中心扩展法（时间复杂度O(n²)）或Manacher算法（时间复杂度O(n)），不过这两种方法不属于递归解法的范畴。

内容的提问来源于stack exchange，提问作者Cancode