递归：最长回文子串

Question

这是一个非常常见的问题，我们必须找到最长的子串，它也是给定输入字符串的回文子串。

现在有多种可能的方法，我知道动态编程解决方案，从中间扩展等。所有这些解决方案都应该用于任何实际用例。

我正在尝试使用递归来解决这个问题并尝试实现这个简单的想法。

让我们假设 s 是给定的输入字符串，i 和 j 表示输入字符串的任何有效字符索引。因此，如果 s[i] == s[j]，我最长的子串将是：

s.charAt(i) + longestSubstring(s, i + 1, j - 1) + s.charAt(j)

如果这两个字符不相等则：

max of longestSubstring(s, i + 1, j) or longestSubstring(s, i, j - 1)

我尝试在下面实施此解决方案：

// end is inclusive
private static String longestPalindromeHelper(String s, int start, int end) {
    if (start > end) {
        return "";
    } else if (start == end) {
        return s.substring(start, end + 1);
    }
    // if the character at start is equal to end
    if (s.charAt(start) == s.charAt(end)) {
        // I can concatenate the start and end characters to my result string
        // plus I can concatenate the longest palindrome in start + 1 to end - 1
        // now logically this makes sense to me, but this would fail in the case
        // for ex: a a c a b d k a c a a (space added for visualization)
        // when start = 3 (a character)
        // end = 7 (again end character)
        // it will go in recursion with start = 4 and end = 6 from now onwards
        // there is no palindrome substrings apart from the single character
        // substring (which are palindrome by itself) so recursion tree for
        // start = 3 and end = 7 would return any single character from b d k
        // let's say it returns b so result would be a a c a b a c a a
        // this would be correct answer for longest palindrome subsequence but
        // not substring because for sub strings I need to have consecutive
        // characters
        return s.charAt(start)
                + longestPalindromeHelper(s, start + 1, end - 1) + s.charAt(end);
    } else {
        // characters are not equal, increment start
        String s1 = longestPalindromeHelper(s, start + 1, end);
        String s2 = longestPalindromeHelper(s, start, end - 1);
        return s1.length() > s2.length() ? s1 : s2;
    }
}

public static String longestPalindrome(String s) {
    return longestPalindromeHelper(s, 0, s.length() - 1);
}

public static void main(String[] args) throws Exception {
    String ans = longestPalindrome("aacabdkacaa");
    System.out.println("Answer => " + ans);
}

暂时让我们忘记时间复杂度或运行时间。我专注于让它适用于上面的简单案例。正如您在评论中看到的那样，我知道为什么会失败，但我努力按照完全相同的方法纠正问题。我不想在这里使用循环。

以下相同方法可能的修复方法是什么？

注意：我感兴趣的是作为答案的实际字符串，而不是长度。仅供参考，我查看了所有其他问题，似乎没有人遵循这种正确性方法，所以我正在尝试。

Answer 1

一旦你有一个调用，其中 s[i] == s[j]，你可以翻转一个布尔标志或切换到一个修改的方法，该方法与子调用通信，他们不能再使用“不匹配，尝试 i + 1 和 j - 1" 分支（else 条件）。这确保您在递归的剩余部分查看子字符串，而不是子序列。

其次，对于子字符串变体，即使 s[i] == s[j]，您也应该尝试 i + 1 和 j - 1，就好像这些字符不匹配一样，因为其中一个或两个字符可能不是 i 和 j 之间的最终最佳子串的一部分。在子序列版本中，没有任何理由不将任何匹配字符添加到 i 到 j 范围内的当前回文子序列，但子字符串并非总是如此。

例如，给定输入 "aabcbda" 并且我们处于 i = 1 和 j = length - 1 的调用帧，我们需要最大化三种可能性：

最佳子字符串包含两个 'a' 个字符。调用带有标志的子例程，该标志表示我们必须从两端向下消费并且不能再尝试跳过字符。
最好的子字符串可能仍然包括 s[i] 但不包括 s[j]，试试 j - 1.
最好的子字符串可能仍然包括 s[j] 但不包括 s[i]，试试 i + 1.

另一个观察：将最佳索引传递到辅助调用链上可能更有意义，然后在包装函数的最后根据这些索引获取最长的回文子串。

类似地，如果您遇到困难，您可以简化问题并使用递归方法 return 最长回文子串长度，然后切换到获取实际子串本身。这使得更容易专注于子序列逻辑，而不用 return 值使事情复杂化。

Answer 2

在这里使用循环比递归更容易，像这样：

public static void main(String[] args) {
    System.out.println(longestPalindrome("abbqa")); // bb
    System.out.println(longestPalindrome("aacabdkacaa")); // aca
    System.out.println(longestPalindrome("aacabdkaccaa")); // acca
}

public static String longestPalindrome(String str) {
    String palindrome = "";
    for (int i = 0; i < str.length(); i++) {
        for (int j = i; j < str.length(); j++) {
            String substring = str.substring(i, j);
            if (isPalindrome(substring)
                    && substring.length() > palindrome.length()) {
                palindrome = substring;
            }
        }
    }
    return palindrome;
}

public static boolean isPalindrome(String str) {
    for (int i = 0; i < str.length() / 2; i++) {
        if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
            return false;
        }
    }
    return true;
}

递归：最长回文子串

Recursion: Longest Palindrome Substring

java

string

recursion

dynamic-programming