[leetcode]5. 最长回文子串

题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

• 示例 1：
  输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
• 示例 2：
  输入: "cbbd" 输出: "bb"

笨办法：
最初的想法还是暴力破解，但暴力破解的方法显然代价很高。但在没有其它更好方法的情况下，可以先试着把暴力破解的方法写出来。关键是回文数的判定方法，假设存在字符串s为回文字符串，则s[0]=s[length-1]、s[1]=s[length-2]……。但是这种判定方式太过冗长，于是想到第二种判定方法s=s[::-1]，即字符串反转之后依然是自身。

聪明方法：
想到s=s[-1::-1]，就突然反应出来可以用动态规划（DP）来做，这不就是求s和s[::-1]的最大公共子串吗。画个矩阵就做出来了，具体的计算公式如下：

• 当对应的字符相同时，当前公共子串的长度为：m[i-1][j-1]+1
• 当对应的字符不同时，当前公共子串的长度为：0

还有个问题没有考虑到：
如果字符串里正好包含两个相互倒序的子串，将整个字符串倒序后，找到的最大公共子串可能是这两个相互反序的子串。例如：字符串"aacdefcaa"中包含"aac"和"caa"两个子串，整个字符串倒序后，最大公共子串为aac。
可以考虑排除这种情况，也就是每次检测到最大公共子串的时候，检验这个子串是否为回文字符串，如果是才记录，不是则丢弃。

超时的问题：
代码总算是对了，但是超时了，DP的时间复杂度是O(n^2)。难道还有比DP时间复杂度更小的解法？还真有个Manacher's ALGORITHM，本篇先不讨论。
可以对全部相同的子串或者循环子串单独处理，提升处理速度，最终总算是通过了测试。但速度是相当的慢，明明总体思路和官方给出的思路是一致的啊，都用的DP，有空再研究下Manacher's ALGORITHM吧，据说时间复杂度是O(n)。

代码如下：

import numpy as np
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n=len(s)
        m=np.zeros((n,n))
        sr=s[::-1]
        tmpl,maxl=0,0
        tmps,maxs="",""
        if s==sr:
            return s
        for i,vi in enumerate(s):
            for j,vj in enumerate(sr):
                if vi==vj:
                    if i>=1 and j>=1:
                        m[i][j]=m[i-1][j-1]+1
                    else:
                        m[i][j]=1
                # else:
                #     m[i][j]=0
                if m[i][j]>maxl:
                    tmpl=m[i][j]
                    tmps=s[int(i-tmpl+1):(i+1)]
                    # 检验子串是否为回文子串
                    if tmps[::-1]==tmps:
                        maxl=m[i][j]
                        maxs=tmps
        return maxs