資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢最長迴文子串的長度
假設我們有一個字串 S。我們需要找到 S 中最長迴文子串的長度。我們假設字串 S 的長度為 1000。所以如果字串是“BABAC”，那麼最長迴文子串是“BAB”，長度為 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個與字串長度相同的方陣，並將其全部填充為 False
將主對角線元素設定為 True，因此對於所有從 0 到 order – 1 的 i，DP[i, i] = True
start := 0
for l in range 2 to length of S + 1
for i in range 0 to length of S – l + 1
end := i + l
如果 l = 2，則
如果 S[i] = S[end - 1]，則
DP[i, end - 1] = True，max_len := l，並且 start := i
否則
如果 S[i] = S[end - 1] 且 DP[i + 1, end - 2]，則
DP[i, end - 1] = True，max_len := l，並且 start := i
返回 max_len
讓我們看看下面的實現以更好地理解：
示例
class Solution(object):
def solve(self, s):
dp = [[False for i in range(len(s))] for i in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2,len(s)+1):
for i in range(len(s)-l+1):
end = i+l
if l==2:
if s[i] == s[end-1]:
dp[i][end-1]=True
max_length = l
start = i
else:
if s[i] == s[end-1] and dp[i+1][end-2]:
dp[i][end-1]=True
max_length = l
start = i
return max_length
ob = Solution()
print(ob.solve('BABAC'))輸入
"ABBABBC"
輸出
5
更新於： 2020年10月10日
557 次檢視
廣告