解題思路
解法一：暴力法（超時(shí)）
根據(jù)回文子串的定義刻获，枚舉所有長度大于等于2的子串罐脊，依次判斷它們是否是回文承绸；
在具體實(shí)現(xiàn)時(shí)褐望，可以只針對大于“當(dāng)前得到的最長回文子串長度”的子串進(jìn)行“回文驗(yàn)證”勒庄；
在記錄最長回文子串的時(shí)候，可以只記錄“當(dāng)前子串的起始位置”和“子串長度”瘫里，不必做截取实蔽。
步驟：
1)對長度小于2的字符串進(jìn)行特判；
2)枚舉所有長度大于等于2的字符串谨读，并判斷其是否是回文局装，這里可以單獨(dú)寫一個(gè)判斷是否是回文的函數(shù)
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(N^3)，這里 N 是字符串的長度漆腌，枚舉字符串的左邊界贼邓、右邊界阶冈，然后繼續(xù)驗(yàn)證子串是否是回文子串闷尿，這三種操作都與 N 相關(guān)；
空間復(fù)雜度：O(1)女坑，只使用到常數(shù)個(gè)臨時(shí)變量填具，與字符串長度無關(guān)。
解法二：動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃”最關(guān)鍵的步驟是想清楚“狀態(tài)如何轉(zhuǎn)移”匆骗，事實(shí)上劳景，“回文”是天然具有“狀態(tài)轉(zhuǎn)移”性質(zhì)的：一個(gè)回文去掉兩頭以后，剩下的部分依然是回文（這里暫不討論邊界）碉就。
因此盟广，從回文串的定義展開討論：
1、如果一個(gè)字符串的頭尾兩個(gè)字符都不相等瓮钥，那么這個(gè)字符串一定不是回文串筋量；
2烹吵、如果一個(gè)字符串的頭尾兩個(gè)字符相等，才有必要繼續(xù)判斷下去桨武。
（1）如果里面的子串是回文肋拔，整體就是回文串；
（2）如果里面的子串不是回文串呀酸，整體就不是回文串凉蜂。
即在頭尾字符相等的情況下，里面子串的回文性質(zhì)據(jù)定了整個(gè)子串的回文性質(zhì)性誉，這就是狀態(tài)轉(zhuǎn)移窿吩。因此可以把“狀態(tài)”定義為原字符串的一個(gè)子串是否為回文子串。
第一步错览，定義狀態(tài)
dp[i][j] 表示子串 s[i, j] 是否為回文串爆存；
第二步，狀態(tài)轉(zhuǎn)移方程
dp[i][j] = {(s[i] == s[j]) and dp[i+1][j-1]}
分析此方程蝗砾，
1）“動(dòng)態(tài)規(guī)劃”事實(shí)上是在填一張二維表格先较，i 和 j 的關(guān)系是 i <= j ，因此悼粮，只需要填這張表的上半部分闲勺；
2）看到 dp[i + 1][j - 1] 就得考慮邊界情況。dp[i+1][j-1] 的邊界情況是 [i+1, j-1] 不構(gòu)成區(qū)間扣猫，即長度小于2菜循，也即 j - 1- ( i + 1 ) + 1 < 2，即 j - i < 3申尤，也就是說子串 s[i, j] 長度等于2或3癌幕。這時(shí)候，其實(shí)只需要判斷一下頭尾兩個(gè)字符是否相等就可以直接下結(jié)論了昧穿。
如果子串 s[i + 1, j - 1] 只有 1 個(gè)字符勺远，即去掉兩頭，剩下中間部分只有 1 個(gè)字符时鸵，當(dāng)然是回文胶逢；
如果子串 s[i + 1, j - 1] 為空串，那么子串 s[i, j] 一定是回文子串饰潜。
因此初坠，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下結(jié)論彭雾，dp[i][j] = true碟刺，否則才執(zhí)行狀態(tài)轉(zhuǎn)移。
第三步薯酝，初始化
初始化的時(shí)候半沽，單個(gè)字符一定是回文串身诺，因此把對角線先初始化為 1，即 dp[i][i] = 1 抄囚。事實(shí)上霉赡，初始化的部分都可以省去。因?yàn)橹挥幸粋€(gè)字符的時(shí)候一定是回文幔托，dp[i][i] 根本不會(huì)被其它狀態(tài)值所參考穴亏。
第四步，輸出
只要一得到 dp[i][j] = true重挑，就記錄子串的長度和起始位置嗓化，沒有必要截取，因?yàn)榻厝∽址惨男阅苊В涗洿藭r(shí)的回文子串的“起始位置”和“回文長度”即可刺覆。
下面是編碼的時(shí)候要注意的事項(xiàng)：總是先得到小子串的回文判定，然后大子串才能參考小子串的判斷結(jié)果史煎。具體思路是：
1谦屑、在子串右邊界 j 逐漸擴(kuò)大的過程中，枚舉左邊界可能出現(xiàn)的位置篇梭；
2氢橙、左邊界枚舉的時(shí)候可以從小到大，也可以從大到小恬偷。
for j in range(1,size):
for i in range(0,j):
for j in range(1,size):
for i in range(j-1,-1,-1):
或者是：
1悍手、在子串左邊界 i 逐漸擴(kuò)大的過程中，枚舉右邊界可能出現(xiàn)的位置袍患；
2坦康、右邊界枚舉的時(shí)候可以從小到大，也可以從大到小诡延。
for i in range(size-2,-1,-1):
for j in range(i+1,size):
for i in range(size-2,-1,-1):
for j in range(size-1,i,-1):
步驟：
1)對長度小于2的字符串進(jìn)行特判滞欠；
2)初始化一個(gè)二維dp數(shù)組，初值全部為 False孕暇；
3)設(shè)置兩個(gè)迭代變量仑撞，即最大回文子串起始點(diǎn)和其長度，可分別設(shè)置為 0 和 1妖滔；
4)根據(jù)轉(zhuǎn)移方程，進(jìn)行動(dòng)態(tài)規(guī)劃桶良；
5)最后返回迭代變量所記錄的最大回文子串即可座舍。
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n^2) 。
空間復(fù)雜度：O(n^2)陨帆，該方法使用 O(n^2)的空間來存儲(chǔ)表曲秉。
代碼
解法一：暴力法（超時(shí)）
class Solution:
def isPalindrome(self, s, left, right):
while left<right:
if s[left] !=s[right]:
return False
left += 1
right -= 1
return True
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size<2:
return s
max_len = 0
res = s[0]
for i in range(0, size-1):
for j in range(i+1, size):
if (j-i+1)>max_len and self.isPalindrome(s, i, j):
max_len = j-i+1
res = s[i:j+1]
return res
解法二：動(dòng)態(tài)規(guī)劃
class Solution:
def longestPalindrome(self, s: str) -> str:
size = len(s)
if size<2:
return s
dp = [[False for _ in range(size)] for _ in range(size)]
max_len = 1
start = 0
# 這部分可有可無
# for i in range(size):
# dp[i][i] = True
for i in range(size-2,-1,-1):
for j in range(i+1, size):
if s[i]==s[j]:
if j-i<3:
dp[i][j]=True
else:
dp[i][j]=dp[i+1][j-1]
else:
dp[i][j]=False
if dp[i][j]:
cur_len = j-i+1
if cur_len>max_len:
max_len = cur_len
start = i
return s[start:start+max_len]
