使用Python找出最长回文子序列长度的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设，我们得到一个字符串。我们必须找出一个偶数长度的回文子序列，除了中间不包含两个连续的相同字符。我们必须返回这种类型的子串的长度作为输出。

因此，如果输入类似于 s = 'efeffe'，则输出将为 4

输出为 4，因为只有一个长度为偶数的回文子序列。字符串是长度为 4 的 'effe'。

为了解决这个问题，我们将按照以下步骤操作 -

  • n := s 的大小

  • dp := 一个 nxn 二维数组，其中每个项目都是形式为 (0, 空白字符串) 的一对

  • 对于 n-1 到 -1 范围内的 i，减 1，做

    • 如果 s[i] 与 s[j] 相同并且 dp[i+1, j-1] 的字符串不是 s[i]，则

    • 否则，

    • 返回存储在 dp[0, n-1] 的对的第一个元素

    • dp[i, j] := 配对（dp[i+1, j-1] + 2, s[i] 的第一个元素）

    • dp[i, j] := 在 (dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) 中选择第一个元素对的最大值

    • 对于 i+1 到 n 范围内的 j，做

    让我们看看以下实现以获得更好的理解 -

    示例

    def solve(s):
       n = len(s)
       dp = [[(0, '')]*n for _ in range(n)]
       for i in range(n-1, -1, -1):
          for j in range(i+1, n):
             if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
                dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
             else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
       return dp[0][n-1][0]
    print(solve('efeffe'))

    输入

    'efeffe'
    输出结果
    4

    以上是 使用Python找出最长回文子序列长度的程序 的全部内容， 来源链接： utcz.com/z/360677.html

    回到顶部