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)的二維陣列，並用0填充

  • 對於i從(n + m - 1)到0遞減，執行：

    • 對於j從i到(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

  • 對於i從0到n-1，執行：

    • 對於j從m-1到-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

更新於：2021年10月8日

瀏覽量：128

啟動你的職業生涯

完成課程獲得認證

開始學習
廣告