資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式檢查字串是否可以拆分為三個迴文
假設我們有一個字串 s。我們需要檢查是否可以將 s 拆分為三個迴文子字串。
因此，如果輸入類似於 s = "levelpopracecar"，則輸出將為 True，因為我們可以將其拆分為 "level"、"pop"、"racecar"，它們都是迴文。
為了解決這個問題，我們將遵循以下步驟：
n := s 的大小
dp := 一個 n x n 階矩陣，並填充為 false
對於 i 從 n-1 到 0，遞減 1，執行
對於 j 從 0 到 n - 1，執行
如果 i >= j，則
dp[i, j] := True
否則，當 s[i] 與 s[j] 相同，則
dp[i, j] := dp[i+1, j-1]
對於 i 從 1 到 n - 1，執行
對於 j 從 i+1 到 n - 1，執行
如果 dp[0, i-1] 和 dp[i, j-1] 和 dp[j, n-1] 都為真，則
返回 True
返回 False
示例
讓我們看看以下實現以更好地理解
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))輸入
"levelpopracecar"
輸出
True
更新於: 2021年10月7日
517 次檢視
廣告