求最大回文子串(2)
发布时间
阅读量：
阅读量
之前采用动态规划法对这一问题进行了求解如何求字符串里的最长回文子串,尽管动态规划法在处理许多复杂问题时表现优异,但在解决该问题时,其时间复杂度显然存在较大缺陷.因此,此次尝试引入其他算法方案,旨在改善动态规划法在时间效率方面的不足.首先将介绍中心扩展法这一方法.
先展示代码实现,再进行理论分析.
#中心扩展法求回文字符串问题
class GetPalindromeStr:
def __init__(self):
#保存最终的最大回文子串的起始索引和长度
self.startIndex = -1
self.lens = 0
def getStartIndex(self):
return self.startIndex
def getLens(self):
return self.lens
'''
对字符串strs,以c1, c2为中心向两边扩展,查找最大长度的回文字符串
'''
def expand(self, strs, c1, c2):
n = len(strs)
while c1 >= 0 and c2 < n and strs[c全部评论 (0)
还没有任何评论哟~