Chương trình tìm tối đa độ dài palindrome từ các chuỗi con bằng Python

Giả sử chúng ta có hai chuỗi, s và t. Chúng tôi muốn tạo một chuỗi theo cách sau -

• Chọn một số sub1 của dãy con không trống từ s.

• Chọn một số sub2 của dãy con không trống từ t.

• Nối sub1 và sub2 để tạo thành chuỗi.

Chúng ta phải tìm độ dài của palindrome dài nhất có thể được hình thành trong trình mô tả. Nếu chúng tôi không thể tạo bất kỳ palindrome nào, thì hãy trả về 0.

Vì vậy, nếu đầu vào là s =​​"hillrace" t ="cargame", thì đầu ra sẽ là 7 vì chúng ta có thể lấy "race" từ s và "car" từ r, vì vậy "racecar" là palindrome có độ dài 7 .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t

• từ:=s + t

• dp:=tạo một mảng 2D có kích thước (n + m) x (n + m) và điền bằng 0

• đối với tôi trong phạm vi (n + m - 1) đến 0, giảm đi 1, thực hiện

  • đối với j trong phạm vi i đến n + m - 1, thực hiện

    • nếu tôi giống với j, thì

      • dp [i, j]:=1

    • ngược lại khi từ [i] giống với từ [j] thì

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

    • nếu không,

      • dp [i, j] =tối đa dp [i + 1, j] và dp [i, j - 1]

• ans:=0

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • đối với j trong phạm vi m - 1 đến -1, giảm 1, thực hiện

    • nếu s [i] giống với t [j] thì

      • ans =tối đa ans và dp [i, n + j]

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

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))

Đầu vào

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

Đầu ra

7