题目描述：
给定一个字符串 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
