|
Python最长回文子串
变体
返回str中最长回文子串的长度给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添加的最短字符串 
要求
解决原问题和变体问题的时间复杂度为O（N）
思路
写的很好的博客： Manacher’s Algorithm 马拉车算法 全套解法
个人见解
看了上面的博客，第一个Manacher‘s算法总感觉有点瑕疵，关键代码部分阅读起来有点吃力，也许是我太菜了。下面我将给出一个讲解非常好的资料，《来自于程序员代码面试指南：IT名企算法与数据结构题目最优解》
解答
感觉文中有些笔误的地方，用蓝色线画出了一下，添加了我的理解，如果是我理解错了，请指出万分感谢。 万事开头难，如果是第一次了解这个算法的话，多花点时间看一看。 我花了半天好好的研究了一下，以后再复习会更快。 建议：
当你看了半天看的有点糊涂的时候，就告诉自己，博主这样的菜鸡儿，都能你也可以。在当你觉得已经了解大概思路，但是发现这篇文章还有这么长的时候，你就要告诉自己，我都已经了解了过程了，我到底要看看你剩下的篇幅啰嗦啥呢！！！坚持读下去你会受益匪浅哦。
              对于进阶问题2，上述讲的就是进阶问题1. 很显然本题和进阶问题基本一致，有index，有半径能唯一确定这个最长回文。  
Python 实现
class Solution:
def manacherString(self,s):
charArr = list(s)
res = []
index = 0
for i in range(0, len(charArr) * 2 + 1):
if (i & 1) == 0:
res.append("#")
else:
res.append(charArr[index])
index += 1
return res
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# if s is None or len(s) == 0:
# return None
charArr = self.manacherString(s)
pArr = []
index = -1
pR = -1
max_value = -11111
# maxContainsEnd = -1
for i in range(0,len(charArr)):
if pR > i:
pArr.append(min(pArr[2*index -i],pR-i))
else:
pArr.append(1)
while i + pArr[i] < len(charArr) and i - pArr[i] > -1:
if charArr[i + pArr[i]] == charArr[i - pArr[i]]:
pArr[i] += 1
else:
break
if i + pArr[i] > pR:
pR = i + pArr[i]
index = i
max_value = max(max_value, pArr[i])
result1 = pArr.index(max_value)
result2 = charArr[result1-max_value+1:result1+ max_value]
for i in range(0,len(result2),2):
result2.remove('#')
result2 = ''.join(result2)
return result2
#leetcode Test 最快的答案
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 2 or s == s[::-1]:
return s
max_len = 1
start = 0
for i in range(1,len(s)):
even = s[i - max_len : i + 1]
odd = s[i - max_len - 1 : i + 1]
if i - max_len - 1 >= 0 and odd == odd[::-1]:
start = i - max_len - 1
max_len += 2
continue
if i - max_len >= 0 and even == even[::-1]:
start = i - max_len
max_len += 1
return s[start : start + max_len]
动态规划求解
 上面的原文地址：
另外的变体题目
回文子序列问题 https://www.cnblogs.com/AndyJee/p/4465696.html
|