LeetCode#5 Longest Palindromic

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
找出回文序列
看了答案中动态规划的思想，觉得有点问题，没想通，看了Chomolungma 的解法，还挺妙的。
解法是基于回文本身的特性：对于任意串中一个最大的回文序列，增加一个字符，只可能让回文序列长度增加0，1或者2，比如s='abb'，最大回文序列长度maxlen是2，如果增加字符'c'，maxlen＝2，如果增加字符'b'，maxlen＝3，如果增加字符'a'，maxlen＝4。
另：任意字符s='a'的回文序列长度maxlen＝1
求解思路就是从串的第一个字符开始，每次增加一个字符，判断是否产生回文序列，保存最大的回文序列长度和起始位置。
在判断回文序列时，作者直接用list逆序，另外，用list取下标list[1:1000],不会out of index

def longestPalindrome(self, s):
    start = 0
    maxlen = 1
#当前字符i是当前回文序列的最后一个字符
    for i in range(len(s)):
        #先看增加一个字符之后长度会不会加2，即判断从当前最大回文序列的前一个字符开始到后一个字符是不是回文
        if (i-maxlen-1>=0 & s[i-maxlen-1:i+1] == s[i-maxlen-1:i+1][::-1]:
            start = i-maxlen-1
            maxlen+=2
            #如果长度能加2 就不考虑长度加1的情况，继续
            continue
        if(i-maxlen>=0 &s[i-maxlen:i+1] == s[i-maxlen:i+1][::-1]:
            start = i-maxlen
            maxlen+=1
    return s[start:start+maxlen]

看了一个马拉车算法，柑橘马拉车算法也是充分分析了回文序列特征之后写出来的。没看到有python的动态规划版本。。。

def longestPalindrome(self, s):
#处理字符：abc->^#a#b#c#,这种字符的回文序列都有一个中心字符
    T = ('#').join('^{}',s)
    C,R=0
    n=len(T)
#保存中心字符到当前最大回文序列最右端的距离
    P=[0]*n
    for i in range(1,n):
        #2*C-i表示i关于C的对称点下标，如果i在某个最大回文序列内部即R>i 时，以i为中心的最大回文序列到最右端的距离P[i]=P[2*C-i],并且最大只能是R-i。
        P[i]= (R>i) and min(R-i,P[2*C-i]) 
        #扩充当前以i为中心的回文序列
        #在当前回文序列两边添加一个字符，判断是不是回文
        while T[i+1+P[i]] == T[i-1-P[i]]:
                P[i] += 1
#比较以i为中心的最大回文序列和当前以C为中心的最大回文序列，保存大的
        if i+P[i]>R:
            C,R = i,i+P[i]
    center, length = max((cen,leng) for cen,leng in enumerate(P)
return s[(center-length)//2:(center+length)//2]