如何修改Java递归计算最长回文子串长度的代码以返回实际子串

现有递归实现的helper方法仅能返回最长回文子串的长度，需要调整代码逻辑，使其直接返回最长回文子串的实际内容，对应测试场景要求：

• 输入字符串"babaddab"，预期返回最长回文子串"baddab"（长度6）
• 输入字符串"cbbd"，预期返回最长回文子串"bb"（长度2）

原有长度计算代码如下：

String s ="babaddab";
int len=s.length() ;
helper(s,0,len-1); //call

public static int helper(String s ,int i ,int j)
{
    if(i==j)
    return 1;
    if(i >j)
    return 0;
    if( s.charAt(i)==s.charAt(j) )
    {
        return 2 + helper(s,i+1,j-1);
    } else 
    {
        return   Math.max(helper(s,i+1,j),helper(s,i,j-1));
    }
}

核心调整思路是将递归方法的返回值从int长度类型改为String类型，递归过程中直接返回当前区间内的最长回文子串，不需要额外维护长度变量，长度可直接通过返回字符串的length()方法获取。

修改后完整可运行代码 #

public class LongestPalindromeTest {
    public static void main(String[] args) {
        // 测试用例验证
        String s1 = "babaddab";
        System.out.println(helper(s1, 0, s1.length() - 1)); // 输出 baddab
        String s2 = "cbbd";
        System.out.println(helper(s2, 0, s2.length() - 1)); // 输出 bb
    }

    public static String helper(String s, int i, int j) {
        // 边界1：区间只剩单个字符，本身就是回文
        if (i == j) {
            return String.valueOf(s.charAt(i));
        }
        // 边界2：区间为空，返回空字符串
        if (i > j) {
            return "";
        }
        if (s.charAt(i) == s.charAt(j)) {
            // 首尾字符匹配，拼接在内层回文的两侧
            String inner = helper(s, i + 1, j - 1);
            return s.charAt(i) + inner + s.charAt(j);
        } else {
            // 首尾不匹配，分别取缩左、缩右区间的结果，返回更长的那个
            String leftShiftRes = helper(s, i + 1, j);
            String rightShiftRes = helper(s, i, j - 1);
            return leftShiftRes.length() > rightShiftRes.length() ? leftShiftRes : rightShiftRes;
        }
    }
}

逻辑说明 #

• 边界场景直接返回对应内容：单字符区间返回字符本身，空区间返回空串，和原长度计算的边界逻辑完全对齐
• 首尾字符相等时，将两个匹配字符拼接在内层递归返回的回文串首尾，构成更长的回文串
• 首尾字符不等时，分别递归计算左指针右移、右指针左移两个子区间的最长回文，选择长度更长的结果返回

注：纯递归实现存在重复子问题计算，处理长字符串时可新增二维记忆数组，存储已经计算过的[i,j]区间结果，减少重复递归提升运行效率。

内容的提问来源于stack exchange，提问作者Pale Blue Dot