Python 刷题日记：LeetCode 5&9&516，pythonleetcode

原题：LeetCode 5
Longest Palindromic Substring:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: “aba” is also a valid answer.
Example:

Input: "cbbd"

Output: "bb"

LeetCode 5和516其实就是一道题，一个求最长回文字串，一个求最长回文字串的长度。第9题比较简单，问如何证明一个整数是否是回文。先解决5和516，最后给出9.

解题思路：

1、字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串，并且判断这个子串是否为回文串，这个算法的时间复杂度为O(n^3)的。这种最差的方案我就不给出代码了。
2、稍微优化的一个算法是枚举回文串的中点，这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，枚举中点再判断是否是回文串，这样能把算法的时间复杂度降为O(n^2)，但是当n比较大的时候仍然无法令人满意。这种方案理解起来比较简单。下面先给出这种方案解决方法。
3、最后给出一种复杂度为O(n)的Manacher算法。

Solution1:

思路：
对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）往两边同时进行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂度为O(n),所以时间复杂度为O((2*n-1)*n)=O(n^2),空间复杂度为O(1)。
Tips: 这样解决可以把奇偶相对统一起来，一起解决。

def longestPalindrome4(s):
    len_s=len(s)
    if len_s==0:
        return ''
    maxlen=0
    res=''
    for i in range(2*len_s-1):
        left=i/2          #i 能被2整除的  都是原来字符串里的字符
        right=i/2
        if i%2==1:            #这个i代表的字符为字符之间的间隙
            right=right+1
        sample_s=lengthOfPalindrome(s,left,right)
        if maxlen<len(sample_s):
            maxlen=len(sample_s)
            res=sample_s

    return res

##寻找以left和right为中心的最长回文子串
def lengthOfPalindrome(s,left,right):

    while (left>=0 and right<len(s) and s[left]==s[right]):
        left=left-1
        right=right+1

    return s[left+1:right]

Solution2:

Manacher算法，这是一种比较有效的方法解决最长回文子串问题，但是没接触过的同学，比较难理解。Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串，达到了理论上的下界。
具体算法参考了ddyyxx的博客。理论部分如下，代码重新用python实现了一遍。

Manacher算法

算法总结第三弹 manacher算法，前面讲了两个字符串相算法——kmp和拓展kmp，这次来还是来总结一个字符串算法，manacher算法，我习惯叫他 “马拉车”算法。

相对于前面介绍的两个算法，Manacher算法的应用范围要狭窄得多，但是它的思想和拓展kmp算法有很多共通支出，所以在这里介绍一下。Manacher算法是查找一个字符串的最长回文子串的线性算法。

在介绍算法之前，首先介绍一下什么是回文串，所谓回文串，简单来说就是正着读和反着读都是一样的字符串，比如abba，noon等等，一个字符串的最长回文子串即为这个字符串的子串中，是回文串的最长的那个。

计算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串，并且判断这个子串是否为回文串，这个算法的时间复杂度为O(n^3)的，显然无法令人满意，稍微优化的一个算法是枚举回文串的中点，这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，枚举中点再判断是否是回文串，这样能把算法的时间复杂度降为O(n^2)，但是当n比较大的时候仍然无法令人满意，Manacher算法可以在线性时间复杂度内求出一个字符串的最长回文字串，达到了理论上的下界。

1.Manacher算法原理与实现

下面介绍Manacher算法的原理与步骤。

首先，Manacher算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号。下面举一个例子：

（1）Len数组简介与性质

Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度，比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。

对于上面的例子，可以得出Len[i]数组为:

Len数组有一个性质，那就是Len[i]-1就是该回文子串在原字符串S中的长度，至于证明，首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。

有了这个性质，那么原问题就转化为求所有的Len[i]。下面介绍如何在线性时间复杂度内求出所有的Len。

（2）Len数组的计算

首先从左往右依次计算Len[i]，当计算Len[i]时，Len[j](0<=j<i)已经计算完毕。设P为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为po，分两种情况：

第一种情况：i<=P

那么找到i相对于po的对称位置，设为j，那么如果Len[j]<P-i，如下图：

那么说明以j为中心的回文串一定在以po为中心的回文串的内部，且j和i关于位置po对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，即Len[i]>=Len[j]。因为Len[j]<P-i,所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。

如果Len[j]>=P-i,由对称性，说明以i为中心的回文串可能会延伸到P之外，而大于P的部分我们还没有进行匹配，所以要从P+1位置开始一个一个进行匹配，直到发生失配，从而更新P和对应的po以及Len[i]。

第二种情况: i>P

如果i比P还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地一个一个匹配了，匹配完成后要更新P的位置和对应的po以及Len[i]。

代码实现：

Manacher算法的时间复杂度分析和Z算法类似，因为算法只有遇到还没有匹配的位置时才进行匹配，已经匹配过的位置不再进行匹配，所以对于T字符串中的每一个位置，只进行一次匹配，所以Manacher算法的总体时间复杂度为O(n)，其中n为T字符串的长度，由于T的长度事实上是S的两倍，所以时间复杂度依然是线性的。

def longestPalindrome3(s):
    mx=0                   #mx即为当前计算回文串最右边字符的最大值
    ans=0
    po=0
    Len=[0]*10000

##转换字符串
    def INIT(s):
        init_s='@#'
        for x in s:
            init_s=init_s+x+'#'

        return init_s+'$',2*len(s)+1     # 字符串结尾加一个字符，防止越界 

    init_s,len_s=INIT(s)       #转换字符串
    get_po=0
    for i in range(1,len_s):
        if mx>i:
            Len[i]=min(mx-i,Len[2*po-i]) #在Len[j]和mx-i 中取小
        else:
            Len[i]=1  #如果i>mx，要从头开始匹配

        while init_s[i-Len[i]]==init_s[i+Len[i]]:
            Len[i]=Len[i]+1

        if Len[i]+i>mx:      #若新计算的回文串右端点位置大于mx，要更新po和mx的值
            mx=Len[i]+i
            po=i


        if ans<Len[i]:
            ans=Len[i]
            get_po=i


    return 'ans=  '+str(ans-1)+'  get_po= '+init_s[get_po-ans+2:get_po+ans:2]   #返回Len[i]中的最大值-1即为原串的最长回文子串额长度

这里的返回值包括最长回文字串的长度和最长回文。

Solution3:

这是一种动态规划的做法：就是外层循环i从后往前扫，内层循环j从i当前字符扫到结尾处。
但是我这里做的有一个问题就是依赖了python的字符串特性，导致复杂极高，不建议用（s==s[::-1]来判断）。

def longestPalindrome3(s):
        """
        :type s: str
        :rtype: str
        """
        len_s=len(s)
        start=0
        end=0
        res=1
        if s==s[::-1]:
            return s
        else:
            print '1'
            i=0
            j=1
            while(i<len_s-res):
                while (j<len_s):
                    sample_s=s[i:j+1]
                    if sample_s==sample_s[::-1]:
                        res=j+1-i
                        start=i
                        end=j
                    j=j+1
                i=i+1
                j=i+res
            return s[start:end+1]

LeetCode 9:

Determine whether an integer is a palindrome. Do this without extra space.

def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False

        else:
            str1 = str(x)
            str2 = str1[::-1]
            if str1 == str2:
                return True
            else:
                return False