如何修改计算最长回文子序列长度的Java代码求最长回文子串长度

现有一段可计算*最长回文子序列（longest palindromic subsequence）长度的Java代码，需要调整代码逻辑，实现最长回文子串（longest palindromic substring）*的长度计算功能。

原有实现代码 #

public static int lp(String str, int i, int j, int ans) {    
    if (i == str.length() || j <= 0)
        return ans;

    if (i > j)
        return ans;

    if (i == j)
        return ans + 1;

    if (str.charAt(i) == str.charAt(j)) {
        int a = lp(str, i + 1, j, ans);
        int b = lp(str, i, j - 1, ans);
        int c = lp(str, i + 1, j - 1, ans + 2);
        ans = Math.max(Math.max(a, b), c);
        return ans;
    } else {
        int a = lp(str, i + 1, j, ans);
        int b = lp(str, i, j - 1, ans);
        ans = Math.max(a, b);
        return ans;
    }
}

原调用示例 #

String s = "sbsncjss"; 
// 该字符串最长回文子序列长度为5，最长回文子串长度为3
System.out.println("Ans is " + lp(s, 0, s.length() - 1, 0));

修改思路 #

首先明确两个概念的核心差异：

• 回文子序列：不需要字符索引连续，允许跳过中间不匹配的字符
• 回文子串：要求选中的字符在原字符串中索引完全连续，只要区间内任意位置不匹配，当前路径累计的长度就直接失效，不能跨不匹配的位置累加长度。

原代码完全适配子序列的非连续规则，要改造成子串计算，核心要解决「跨不匹配位置累加长度」的问题。

修改后可运行代码 #

public static int lp(String str, int i, int j, int ans) {    
    // 边界触达，兜底返回当前累计的最长结果
    if (i >= str.length() || j < 0 || i > j)
        return Math.max(ans, i == j ? 1 : 0);

    if (i == j)
        return Math.max(ans, 1);

    if (str.charAt(i) == str.charAt(j)) {
        int innerLen;
        // 两个相邻字符相等，本身构成长度为2的回文
        if (j == i + 1) {
            innerLen = 2;
        } else {
            // 递归查询内层区间的最长回文长度
            int innerRes = lp(str, i + 1, j - 1, 0);
            // 只有内层区间完全匹配（返回长度等于内层区间总长度），才能和两端字符拼成更长连续回文
            innerLen = (innerRes == j - i - 1) ? innerRes + 2 : Math.max(innerRes, 1);
        }
        // 跳过左端点、跳过右端点搜索的分支，累计长度重置为0，连续串断裂后不能继承之前的计数
        int a = lp(str, i + 1, j, 0);
        int b = lp(str, i, j - 1, 0);
        ans = Math.max(Math.max(a, b), Math.max(ans, innerLen));
        return ans;
    } else {
        // 两端字符不匹配，当前区间不可能构成连续回文，两个搜索分支都重置累计长度从0开始
        int a = lp(str, i + 1, j, 0);
        int b = lp(str, i, j - 1, 0);
        ans = Math.max(ans, Math.max(a, b));
        return ans;
    }
}

用原示例调用修改后的方法，会正确返回最长回文子串长度3。

具体调整点 #

• 修正原边界判断bug：原逻辑j <= 0会漏掉索引0位置的单字符场景，调整为j < 0，同时补全i>j场景下的单字符兜底返回
• 两端字符不匹配时：所有递归分支传入的累计值ans重置为0，只要跳过任意一端，当前连续回文就断裂，继承之前的计数会统计到非连续的子序列结果
• 两端字符匹配时：新增内层连续性校验，只有i+1到j-1整个区间完全是连续回文（返回长度等于区间长度），才能把两端的两个字符计入长度做+2操作；如果内层存在不匹配的断点，两端的相等字符无法和内层拼成连续子串，不能直接累加
• 两端字符匹配时，跳左端点、跳右端点的搜索分支同样重置ans为0，避免统计跨断点的非连续结果
• 所有分支最终都和当前传入的ans取最大值，避免漏掉之前递归流程中找到的更长回文结果

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