Giả sử chúng ta có một chuỗi s. Chúng tôi phải kiểm tra xem chúng tôi có thể chia các s thành ba chuỗi con palindromic hay không.
Vì vậy, nếu đầu vào là s ="levelpopracecar", thì đầu ra sẽ là True vì chúng ta có thể chia nó thành "level", "pop", "racecar", tất cả đều là palindromes.
Để 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:=ma trận bậc n x n và điền sai
-
đối với tôi trong phạm vi n-1 đến 0, giảm 1, thực hiện
-
đối với j trong phạm vi 0 đến n - 1, thực hiện
-
nếu tôi> =j, thì
-
dp [i, j]:=Đúng
-
-
ngược lại khi s [i] giống với s [j] thì
-
dp [i, j]:=dp [i + 1, j-1]
-
-
-
đối với tôi trong phạm vi từ 1 đến n - 1, hãy thực hiện
-
đối với j trong phạm vi i + 1 đến n - 1, thực hiện
-
nếu dp [0, i-1] và dp [i, j-1] và dp [j, n-1] đều đúng thì
-
trả về True
-
-
-
-
-
trả về Sai
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):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(n):
if i >= j:
dp[i][j] = True
elif s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
for i in range(1, n):
for j in range(i+1, n):
if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
return True
return False
s = "levelpopracecar"
print(solve(s)) Đầu vào
"levelpopracecar"
Đầu ra
True