在Python中查找子序列的最大回文长度的程序

在Python中查找子序列的最大回文长度的程序

假设我们有两个字符串s和t。我们希望按以下方式构建字符串−

  • 从s中选择一些非空子序列sub1。

  • 从t中选择一些非空子序列sub2。

  • 将sub1和sub2连接起来,构成字符串。

我们必须找到在上述方式下可以形成的最长回文的长度。如果我们无法形成任何回文,则返回0。

因此,如果输入是s = “hillrace” t = “cargame”,那么输出将是7,因为我们可以从s中取出”race”,从t中取出”car”,因此”racecar”是长度为7的回文。

要解决这个问题,我们将按以下步骤进行−

  • n:s的大小,m:t的大小

  • word:s + t

  • dp:创建一个大小为(n + m) x (n + m)的2D数组并填充为0

  • for i in range (n + m – 1) to 0,倒序循环,执行以下步骤

    • for j in range i to n + m – 1,执行以下步骤
      • 如果i与j相同,则

      • dp[i, j] := 1

      • 否则,当word[i]与word[j]相同时,则

      • dp[i, j] := 2 + dp[i + 1, j – 1]

      • 否则,

      • dp[i, j] = dp[i + 1, j]和dp[i, j – 1]中的最大值

  • ans := 0

  • for i in range 0 to n – 1,执行以下步骤

    • for j in range m – 1 to -1,倒序循环,执行以下步骤
      • 如果s[i]与t[j]相同,则

      • ans = ans和dp[i, n + j]的最大值

  • 返回ans

示例

让我们看看以下实现,以便更好地理解

def solve(s, t):
   n, m = len(s), len(t)
   word = s + t
   dp = [[0] * (n + m) for _ in range(n + m)]

   for i in range(n + m - 1, -1,-1):
      for j in range(i, n + m):
         if i == j:
            dp[i][j] = 1
         elif word[i] == word[j]:
            dp[i][j] = 2 + dp[i + 1][j - 1]
         else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
   ans = 0
   for i in range(n):
      for j in range(m - 1, -1, -1):
         if s[i] == t[j]:
            ans = max(ans, dp[i][n + j])
   return ans

s = "hillrace"
t = "cargame"
print(solve(s, t))

输入

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]

输出

7

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程