005 longest palindromic substring
5. Longest Palindromic Substring
题目:
https://leetcode.com/problems/longest-palindromic-substring/
难度:
Medium
思路0:
暴力解法绝对不行
思路1:
所以一个好的想法是 s 和 reverse(s) 共有的最长的 substring就是longest palindromic substring -> 问题转成求Longest common substring problem
参见wikipedia
，典型动归
LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0
伪码也有了，代码也有：
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2
这样也超时？
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
def lcs(s1, s2):
m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
longest, x_longest = 0, 0
for x in xrange(1, 1 + len(s1)):
for y in xrange(1, 1 + len(s2)):
if s1[x - 1] == s2[y - 1]:
m[x][y] = m[x - 1][y - 1] + 1
if m[x][y] > longest:
longest = m[x][y]
x_longest = x
else:
m[x][y] = 0
return s1[x_longest - longest: x_longest]
return lcs(s, s[::-1])
因为以为这样s[::-1]已经很快了.
这个方法是buggy的，看字符串abcxgcba,它reverse之后是abcgxcba,它们有公共字符串，但是这里面没有回文，修复方式是：
we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.
我觉得的修复方式这样么：
原本 翻转
ABXYBA ABYXBA
求出来的substring indices是 0:2 但是这个s1[0:2] 和 s2[0:2]一样，所以不行
同理common substring indices还是s[4:6] 和s2[4:6]一样，不行
而比如ABAD和 DABA
substring indice 一个是0：3， 一个是1:4，这样就没问题
思路2:
依次把每一个字符当做回文字符串的中间字符，找到以该字符为中间字符的回文串的最大长度。分别对奇偶的情况进行讨论，接下来的关键就是对边界的把握，确保下标不要越界。当子串已经包含首字符或最后一个字符且此时还是回文串的时候，下标分别会向两边多移一位，需要补回来。
参考https://shenjie1993.gitbooks.io/leetcode-python/content/005%20Longest%20Palindromic%20Substring.html
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
# empty or one char
if n < 2:
return s
# left index of the target substring
l = 0
# right index of the target substring
r = 0
# length of the longest palindromic substring for now
m = 0
# length of the current substring
c = 0
# Whether the substring contains the first character or last character and is palindromic
b = True
for i in range(n):
# Odd situation
for j in range(min(n-i,i+1)):
if s[i-j] != s [i+j]:
b = False
break
else:
c = 2 * j + 1
if c > m :
l = i - j + 1 - b
r = i + j + b
m = c
b = True
# Even situation
for j in range(min(n - i - 1, i + 1)):
if (s[i - j] != s[i + j + 1]):
b = False
break
else:
c = 2 * j + 2
if (c > m):
l = i - j + 1 - b
r = i + j + 1 + b
m = c
b = True
return s[l:r]
以上是参考版本，自己写的版本：
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
m,l,r = 0,0,0
for i in range(n):
# odd case
for j in range(min(i+1,n-i)):
if s[i-j] != s[i+j]:
break
if 2*j + 1 > m :
m = 2 * j + 1
l = i-j
r = i+j
if i+1 < n and s[i] == s[i+1]:
for j in range(min(i+1,n-i-1)):
if s[i-j] != s[i+j+1]:
break
if 2 * j + 2 > m :
m = 2*j +2
l = i-j
r = i+j+1
return s[l:r+1]
思路3:
Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。得到一个很重要的结论：
- 如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i) . 为什么这样说呢，下面解释
下面，令j = 2*id - i，也就是说j是i关于id的对称点。
-
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于i和j对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有P[i] = P[j]；
-
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，再具体匹配。
所以P[i] >= Min(P[2 * id - i], mx - i)，因为以j为中心的绘回文子串的左边界可能会比mx关于id的对称点要大，此时只能证明P[i]=P[2 * id - i] - 此外，对于 mx <= i 的情况，因为无法对 P[i]做更多的假设，只能让P[i] = 1，然后再去匹配。
在下面的程序中我的P数组保存的是，以当前字符为回文子串中心时，该回文子串的长度（不包含当前字符自身）
简单地用一个小例子来解释：原字符串为'qacbcaw'，一眼就可以看出来最大回文子串是'acbca'， 下面是我做的图，累shi了！
所以最终代码中的max_i就是字符'b'所对应的index8，start的值就是(max_i - P[max_i] - 1) / 2 = 1,最终输出结果为s[1:6],即‘acbca’
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
def preProcess(s):
if not s:
return ['^', '&']
T = ['^']
for i in s:
T += ['#', i]
T += ['#', '$']
return T
T = preProcess(s)
P = [0] * len(T)
id, mx = 0, 0
for i in range(1, len(T)-1):
j = 2 * id - i
if mx > i:
P[i] = min(P[j], mx-i)
else:
P[i]= 0
while T[i+P[i]+1] == T[i-P[i]-1]:
P[i] += 1
if i + P[i] > mx:
id, mx = i, i + P[i]
max_i = P.index(max(P)) #保存的是当前最大回文子串中心位置的index
start = (max_i - P[max_i] - 1) / 2
res = s[start:start+P[max_i]]
return res
run code的时候结果会跟expected不一样，但是该input确实2个结果都可以，所以放心地submit吧 还可以转到647题去看一看，也可以用这个算法解
