首页 文章

最长的回文子串自上而下动态编程

提问于
浏览 次
1

下面是使用自下而上动态编程给出字符串 s 找到最长回文子串的算法 . 因此，该算法探索所有可能的长度 j substring，并检查它是否是1到n中 j 的有效回文 . 由此产生的时间和空间复杂度为 O(n^2) .

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
    P = [[False for _ in range(n)] for _ in range(n)]
    longest = s[0]

    # j is the length of palindrome
    for j in range(1, n+1):
        for i in range(n-j+1):
            # if length is less than 3, checking s[i] == s[i+j-1] is sufficient
            P[i][i+j-1] = s[i] == s[i+j-1] and (j < 3 or P[i+1][i+j-2])
            if P[i][i+j-1] and j > len(longest):
                longest = s[i:i+j]
    return longest

我试图用自上而下的方法和memoization实现相同的算法 .

Question: 是否可以将此算法转换为自上而下的方法？

关于最长的回文子串有很多问题，但他们大多使用这种自下而上的方法 . https://stackoverflow.com/a/29959104/6217326中的答案似乎与我的想法最接近 . 但答案似乎是使用不同的算法（而且速度要慢得多） .

python dynamic-programming palindrome memoization

1 回答

  • -2

    这是递归的我的解决方案：从i = 0开始，j =最大长度if（i，j）是palindrome：然后max substring length是j-1 . 否则使用（i 1，j）和（i，j-1）进行递归，并在这两者之间取Max . 代码将解释更多：

    public class LongestPalindromeSubstringWithSubStr {
static String str;
static int maxLen;
static int startLen;
static int endLen;
static int dp[][];// 0: not calculaed. 1: from index i to j is palindrome

static boolean isPal(int i, int j) {
    if (dp[i][j] != 0) {
        System.out.println("Res found for i:" + i + " j: " + j);
        return (dp[i][j] == 1);
    }
    if (i == j) {
        dp[i][j] = 1;
        return true;
    }
    if (i + 1 == j) {// len 2
        if (str.charAt(i) == str.charAt(j)) {
            dp[i][j] = 1;
            return true;
        }
        dp[i][j] = -1;
        return false;
    }
    if (str.charAt(i) == str.charAt(j)) {
        boolean res = isPal(i + 1, j - 1);
        dp[i][j] = (res) ? 1 : 0;
        return res;
    }
    dp[i][j] = 0;
    return false;
}

// update if whole string from i to j is palindrome
static void longestPalCalc(int i, int j) {
    if (isPal(i, j)) {
        if (j - i + 1 > maxLen) {// update res
            maxLen = j - i + 1;
            startLen = i;
            endLen = j;
        }
    } else {
        longestPalCalc(i + 1, j);
        longestPalCalc(i, j - 1);
    }
}

public static void main(String[] args) {
    str = "abadbbda";
    dp = new int[str.length()][str.length()];
    longestPalCalc(0, str.length() - 1);
    System.out.println("Longest: " + maxLen);
    System.out.println(str.subSequence(startLen, endLen + 1));
}

    }

    回复于

相关问题