1 題目描述
給定一個(gè)字符串 s ，找出 s 中最長的回文子字符串，字符串的長度不超過1000瓤逼。
示例：
input : 'abab'
out : 'aba'
input : 'abba'
out : 'abba'
2 題目解析
這道題有很多種解法，比較容易理解和實(shí)現(xiàn)钝腺，并且代碼簡單的是“動(dòng)態(tài)規(guī)劃”方法抛姑。
這里我們用到一種表示：dp[i][j]表示字符串 s 中索引值從 i 到 j 的字符是回文字符赞厕。
用公式表示為：
那么這道題的解題過程就是依次遍歷每個(gè)字符艳狐，用dp是否為真判斷從 i 到 j 是不是回文字符串。
3 代碼
class Solution:
def longestPalindrome(self, s):
n = len(s)
if n == 0 or 1:return s
start = end = 0
maxLen = 1
dp = [[False]*n for i in range(n)] #作為容器保存 dp
for j in range(n):
for i in range(j):
# 保證 i 是字串起始皿桑， j 是子串末尾
dp[i][j] = s[i] == s[j] and (j-i<2 or dp[i+1][j-1])
if dp[i][j] and j-i+1 > maxLen:
maxLen = j-i+1
start = i
end = j
dp[i][j] = True
dp[j][j] = True
return s[start: end+1]
string = 'test sub aba'
s = Solution()
s.longestPalindrome(string)
