在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]中的最大值
- for j in range i to n + m – 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]的最大值
- for j in range m – 1 to -1,倒序循环,执行以下步骤
-
返回ans
示例
让我们看看以下实现,以便更好地理解