資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python中最長分塊迴文分解
假設我們有一段文字。我們需要找到最大的k值，使得存在a[1]，a[2]，…，a[k]，滿足以下條件：每個a[i]都是非空字串；它們的連線a[1] + a[2] + ... + a[k]等於給定的文字；對於所有從1到k的i，a[i] = a[{k+1 - i}]。
因此，如果輸入是“antaprezatepzapreanta”，則輸出為11，因為我們可以將其分解為“(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)”。
為了解決這個問題，我們將遵循以下步驟：
start := 0，end := 文字長度 - 1
用空字串初始化temp1和temp2
當文字長度為奇數時，ans = 1，否則為0
當start < end時，執行以下操作：
temp1 := temp1 + text[start]
temp2 := text[end] + temp2
如果temp1等於temp2，則：
將temp1和temp2設定為空字串
ans := ans + 2
start := start + 1
end := end - 1
如果文字長度為偶數並且(temp1或temp2不為空)
ans := ans + 1
返回ans
讓我們看看下面的實現，以便更好地理解：
示例
class Solution(object):
def longestDecomposition(self, text):
start = 0
end = len(text)-1
temp1 = ""
temp2 = ""
ans = 1 if len(text) & 1 else 0
while start<end:
temp1+=text[start]
temp2 = text[end]+temp2
if temp1 == temp2:
temp1 = temp2 = ""
ans+=2
start+=1
end-=1
if len(text)%2 == 0 and(temp1 or temp2):
ans += 1
return ans
ob = Solution()
print(ob.longestDecomposition("antaprezatepzapreanta"))輸入
"antaprezatepzapreanta"
輸出
11
更新於：2020年6月4日
185 次瀏覽
廣告