数据结构
网络
关系数据库管理系统 (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 次浏览
广告