Giả sử, chúng ta được cung cấp một chuỗi. Chúng ta phải tìm ra một dãy con palindromic có độ dài chẵn và không chứa hai ký tự giống nhau liên tiếp ngoại trừ ở giữa. Chúng ta phải trả về độ dài của loại chuỗi con này dưới dạng đầu ra.
Vì vậy, nếu đầu vào là s ='efeffe', thì đầu ra sẽ là 4
Đầu ra là 4 vì chỉ có một dãy con palindromic có độ dài chẵn. Chuỗi là 'effe' có độ dài 4.
Để 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
-
dp:=một n x n mảng 2d trong đó mỗi mục là một cặp ở dạng (0, chuỗi trống)
-
đối với tôi trong phạm vi n-1 đến -1, giảm đi 1, thực hiện
-
đối với j trong phạm vi i + 1 đến n, thực hiện
-
nếu s [i] giống s [j] và chuỗi dp [i + 1, j-1] không phải là s [i] thì
-
dp [i, j]:=tạo một cặp (phần tử đầu tiên của dp [i + 1, j-1] + 2, s [i])
-
-
nếu không,
-
dp [i, j]:=select trong số (dp [i + 1, j], dp [i, j-1], dp [i + 1, j-1]) mà phần tử đầu tiên của cặp là tối đa
-
-
trả về phần tử đầu tiên của cặp được lưu trữ tại dp [0, n-1]
-
-
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(s):
n = len(s)
dp = [[(0, '')]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
return dp[0][n-1][0]
print(solve('efeffe')) Đầu vào
'efeffe'
Đầu ra
4