資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 中的最長迴文子串
假設我們有一個字串 S。我們需要找到 S 中的最長迴文子串。我們假設字串 S 的長度為 1000。所以如果字串是“BABAC”，那麼最長迴文子串是“BAB”。
為了解決這個問題，我們將遵循以下步驟
- 定義一個與字串長度相同的方陣，並用 False 填充它
- 將主對角線元素設定為 True，因此 DP[i, i] = True，對於所有從 0 到 order – 1 的 i
- 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]，則
- 否則
- 如果 S[i] = S[end - 1] 並且 DP[i + 1, end - 2]，則
- DP[i, end - 1] = True，max_len := l，並且 start := i
- 如果 S[i] = S[end - 1] 並且 DP[i + 1, end - 2]，則
- for i in range 0 to length of S – l + 1
- 返回從索引 start 到 start + max_len 的子字串
示例（Python）
讓我們看看以下實現以獲得更好的理解 -
class Solution(object):
def longestPalindrome(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 s[start:start+max_length]
ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))輸入
"ABBABBC"
輸出
"BBABB"
更新於: 2020年4月27日
10K+ 瀏覽量
廣告