最长回文子串长度

Question

下面的代码给出了最长的回文子序列长度。如何修改代码以获得最长的回文子串长度？

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"; 
    // longest subsequence length is 5 and longest substring length is 3
    System.out.println("Ans is " + lp(s, 0, s.length() - 1, 0));

Answer 1

如何修改代码以获得最长的回文子串长度

然后，您需要排除跳过字符的情况。当您的代码即将跳过一个字符时，搜索可以继续，但ans重置为0。

因此：

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, 0);   // <-- reset!
        int b = lp(str, i, j - 1, 0);   // <-- reset!
        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, 0);   // <-- reset!
        int b = lp(str, i, j - 1, 0);   // <-- reset!
        ans = Math.max(a, b);
        return ans;
    }
}

请注意，虽然这是可行的，但有更有效的算法来查找最长的回文子串。但是，它们与您针对最长回文子序列提出的算法完全不同，因此这不仅仅是进行一些更改的问题。