最长回文子序列（Longest Palindromic Subsequence）递归代码错误修复求助

Hey there! Let's start by clearing up a critical mix-up: You said the correct result for input "ABDA" should be 1, but that's actually the answer for the Longest Palindromic Substring (which requires characters to be consecutive). Your current code is built to solve the Longest Palindromic Subsequence (where characters don't need to be adjacent), and for "ABDA", the correct LPS result is 3—think of valid palindromic subsequences like ABA or ADA, both of which are length 3.

If you actually intended to implement a solution for the longest palindromic substring (not subsequence), here's how to adjust your recursive logic:

Why Your Original Code Returns 3 #

First, let's confirm your original code works correctly for LPS:

def lps(s):
    print(s)
    n = len(s)
    if n <= 1:
        return n
    if s[0] == s[n-1]:
        return 2 + lps(s[1:-1])
    return max(lps(s[:-1]), lps(s[1:]))

For "ABDA", it checks that the first and last characters (A and A) match, then adds 2 to the LPS of the middle substring "BD". The LPS of "BD" is 1 (either B or D), so total is 2+1=3—this is correct for LPS.

Fix for Longest Palindromic Substring #

Substrings require consecutive characters, so our recursive logic needs to check if the entire current string is a palindrome first, rather than just matching ends and adding the inner subsequence result. Here's the adjusted code:

def longest_palindromic_substring(s):
    n = len(s)
    if n <= 1:
        return n
    
    # Helper to check if current string is a palindrome
    def is_palindrome(current):
        return current == current[::-1]
    
    if is_palindrome(s):
        return n
    # If not, recurse on the string with either first or last character removed
    return max(longest_palindromic_substring(s[:-1]), longest_palindromic_substring(s[1:]))

Testing this with "ABDA" will return 1, which matches your expected result.

Quick Note on Efficiency #

This recursive approach for substrings has a time complexity of O(2^n), which is pretty slow for longer strings. In practice, most people use dynamic programming or the center expansion method for better performance—but this recursive version works if you're focused on learning the core logic.

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