用 Python 编写程序，从子序列中找出最大回文长度
pythonserver side programmingprogramming更新于 2025/12/13 23:08:17
假设我们有两个字符串，s 和 t。我们想按照以下方式创建一个字符串 −
从 s 中选择一些非空子序列 sub1。
从 t 中选择一些非空子序列 sub2。
连接 sub1 和 sub2，以生成字符串。
我们必须找到可以按照所述方式形成的最长回文的长度。如果我们无法生成任何回文，则返回 0。
因此，如果输入为 s = "hillrace" t = "cargame"，则输出将为 7，因为我们可以从 s 中取出"race"，从 r 中取出"car"，所以"racecar"是长度为 7 的回文。
为了解决这个问题，我们将遵循以下步骤 −
n := s 的大小，m := t 的大小
word := s + t
dp := 创建一个大小为 (n+m) x (n+m) 的二维数组并用 0 填充
对于范围 (n + m - 1) 到 0 内的 i，减少 1，执行
对于范围 i 到 n + m - 1 内的 j，执行
如果 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
对于范围为 0 到 n - 1 的 i，执行
对于范围为 m - 1 到 -1 的 j，减少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 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
