使用Python找出最长回文子序列长度的程序
假设,我们得到一个字符串。我们必须找出一个偶数长度的回文子序列,除了中间不包含两个连续的相同字符。我们必须返回这种类型的子串的长度作为输出。
因此,如果输入类似于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