使用Python编写查找最长回文子序列长度的程序

使用Python编写查找最长回文子序列长度的程序

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

因此,如果输入为s = ‘efeffe’,则输出将为4。

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

为了解决这个问题,我们将遵循以下步骤−

  • n := 字符串s的大小

  • dp := 一个n x n的2D数组,其中每个项是一对元素形成的(0,空字符串)

  • 对于i从n-1到-1的范围进行遍历,执行以下操作

    • 对于j从i+1到n的范围,执行以下操作
      • 如果s [ i ]与s [ j ]相同且dp [ i + 1,j – 1 ]的字符串不是s [ i ],则

      • dp [ i,j ]:=产生一对(first element of dp[i+1, j-1] + 2, s[i])

      • 否则,

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

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

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

例子

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教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程