題目描述：
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

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

笨辦法：
最初的想法還是暴力破解，但暴力破解的方法顯然代價很高。但在沒有其它更好方法的情況下，可以先試著把暴力破解的方法寫出來。關(guān)鍵是回文數(shù)的判定方法，假設(shè)存在字符串s為回文字符串，則s[0]=s[length-1]、s[1]=s[length-2]……。但是這種判定方式太過冗長，于是想到第二種判定方法s=s[::-1]，即字符串反轉(zhuǎn)之后依然是自身。

聰明方法：
想到s=s[-1::-1]，就突然反應(yīng)出來可以用動態(tài)規(guī)劃（DP）來做，這不就是求s和s[::-1]的最大公共子串嗎。畫個矩陣就做出來了，具體的計算公式如下：

• 當(dāng)對應(yīng)的字符相同時，當(dāng)前公共子串的長度為：m[i-1][j-1]+1
• 當(dāng)對應(yīng)的字符不同時，當(dāng)前公共子串的長度為：0

還有個問題沒有考慮到：
如果字符串里正好包含兩個相互倒序的子串，將整個字符串倒序后，找到的最大公共子串可能是這兩個相互反序的子串。例如：字符串"aacdefcaa"中包含"aac"和"caa"兩個子串，整個字符串倒序后，最大公共子串為aac。
可以考慮排除這種情況，也就是每次檢測到最大公共子串的時候，檢驗(yàn)這個子串是否為回文字符串，如果是才記錄，不是則丟棄。

超時的問題：
代碼總算是對了，但是超時了，DP的時間復(fù)雜度是O(n^2)。難道還有比DP時間復(fù)雜度更小的解法？還真有個Manacher's ALGORITHM，本篇先不討論。
可以對全部相同的子串或者循環(huán)子串單獨(dú)處理，提升處理速度，最終總算是通過了測試。但速度是相當(dāng)?shù)穆髅骺傮w思路和官方給出的思路是一致的啊，都用的DP，有空再研究下Manacher's ALGORITHM吧，據(jù)說時間復(fù)雜度是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)]
                    # 檢驗(yàn)子串是否為回文子串
                    if tmps[::-1]==tmps:
                        maxl=m[i][j]
                        maxs=tmps
        return maxs