回文是指正读反读都相同的字符串，例如 "madam" 或 "level"。最长回文子串问题旨在给定一个字符串，找出其中最长的回文子串。例如，对于字符串 "babad"，最长回文子串可以是 "bab" 或 "aba"。本教程将侧重于如何通过递归方式计算最长回文子串的 长度。
递归是解决这类问题的直观方法之一。其基本思路如下：
基于上述思路，一个常见的、但存在缺陷的递归实现可能如下所示：
public static int palindrome(String str) {
str = str.toLowerCase(); // 统一转为小写处理
if (str.length() == 0) {
return 0;
}
if (str.length() == 1) {
return 1;
}
// 如果首尾字符相同
if (str.charAt(0) == str.charAt(str.length() - 1)) {
// 递归检查内部子串的最长回文长度
int innerPalindromeLength = palindrome(str.substring(1, str.length() - 1));
// 这里的逻辑是问题的关键点
// 尝试判断是否整个字符串是回文
if (innerPalindromeLength != 1 || str.length() <= 3) {
// 错误：这个条件不足以判断整个内部子串是否为回文
return 2 + innerPalindromeLength;
}
}
// 如果首尾字符不同，或上述条件不满足，则在子串中寻找
return Math.max(palindrome(str.substring(0, str.length() - 1)),
palindrome(str.substring(1)));
}上述代码中的关键缺陷在于当 str.charAt(0) == str.charAt(str.length() - 1) 时，对内部子串 str.substring(1, str.length() - 1) 的处理。变量 innerPalindromeLength 存储的是 内部子串中最长的回文子串的长度，而不是 内部子串本身是否是一个回文。
考虑以下例子：
正确情况： 字符串 str = "abacaba"。
错误情况： 字符串 str = "abxba"。
被错误处理的情况 (原始代码缺陷所在)： 字符串 str = "abcyba"。
正确的逻辑应该是：当首尾字符相同时，只有当内部子串 完全 构成一个回文时，整个字符串才是一个回文。判断内部子串是否 完全 是回文的条件是：innerPalindromeLength == (str.length() - 2)。
基于上述分析，我们修正递归逻辑如下：
public class PalindromeFinder {
/**
* 递归计算给定字符串中最长回文子串的长度。
*
* @param str 输入字符串
* @return 最长回文子串的长度
*/
public static int findLongestPalindromeLengthRecursive(String str) {
// 统一转为小写处理，忽略大小写差异
str = str.toLowerCase();
// 基线条件
if (str.length() == 0) {
return 0;
}
if (str.length() == 1) {
return 1;
}
// 如果首尾字符相同
if (str.charAt(0) == str.charAt(str.length() - 1)) {
// 获取内部子串 (去除首尾字符)
String innerStr = str.substring(1, str.length() - 1);
// 递归获取内部子串中最长回文的长度
int innerPalindromeLength = findLongestPalindromeLengthRecursive(innerStr);
// 修正后的判断逻辑：
// 只有当内部子串的最长回文长度等于内部子串本身的长度时，
// 才能确定整个字符串是一个回文。
if (innerPalindromeLength == innerStr.length()) {
// 如果内部子串是完整的回文，则当前整个字符串也是回文
return str.length();
}
}
// 如果首尾字符不同，或者首尾相同但内部子串不构成完整回文，
// 则在去除首字符的子串和去除尾字符的子串中寻找最长回文。
return Math.max(findLongestPalindromeLengthRecursive(str.substring(0, str.length() - 1)),
findLongestPalindromeLengthRecursive(str.substring(1)));
}
public static void main(String[] args) {
System.out.println("abacaba -> " + findLongestPalindromeLengthRecursive("abacaba")); // 7
System.out.println("babad -> " + findLongestPalindromeLengthRecursive("babad")); // 3 (bab 或 aba)
System.out.println("cbbd -> " + findLongestPalindromeLengthRecursive("cbbd")); // 2 (bb)
System.out.println("a -> " + findLongestPalindromeLengthRecursive("a")); // 1
System.out.println("racecar -> " + findLongestPalindromeLengthRecursive("racecar")); // 7
System.out.println("abcyba -> " + findLongestPalindromeLengthRecursive("abcyba")); // 3 (bcyb中最长为bcb或byb，所以整体最长是bcb或byb)
System.out.println("abcda -> " + findLongestPalindromeLengthRecursive("abcda")); // 1
System.out.println("madam -> " + findLongestPalindromeLengthRecursive("madam")); // 5
}
}通过递归寻找最长回文子串是一个经典的算法问题，但其实现中隐藏着一个常见的陷阱：对内部子串是否构成完整回文的错误判断。关键在于，当字符串首尾字符相同时，必须确保其内部子串 整体 也是一个回文，才能将整个字符串视为一个更大的回文。正确的判断条件是内部子串的最长回文长度必须等于内部子串本身的长度。虽然递归方法直观，但其效率问题通常促使我们转向动态规划等优化方案。理解并避免此类递归陷阱，是掌握复杂算法设计的重要一步。
以上就是递归求解最长回文子串：一个常见陷阱与修正方案的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
499
收藏
