从 Python 中的子序列中找到最大化回文长度的程序
假设我们有两个字符串,s和t。我们想以下列方式制作一个字符串-
从s中选择一些非空子序列sub1。
从t中选择一些非空子序列sub2。
连接sub1和sub2,以生成字符串。
我们必须找到可以以所描述的方式形成的最长回文的长度。如果我们不能生成任何回文,则返回0。
因此,如果输入类似于s="hillrace"t="cargame",那么输出将是7,因为我们可以从s中获取“race”,从r中获取“car”,所以“racecar”是长度为7的回文.
示例
让我们看下面的实现来更好地理解
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