1 题目描述
给定一个字符串 s ，找出 s 中最长的回文子字符串，字符串的长度不超过1000。
示例：
input : 'abab'
out : 'aba'
input : 'abba'
out : 'abba'
2 题目解析
这道题有很多种解法，比较容易理解和实现，并且代码简单的是“动态规划”方法。
这里我们用到一种表示：dp[i][j]表示字符串 s 中索引值从 i 到 j 的字符是回文字符。
用公式表示为：
那么这道题的解题过程就是依次遍历每个字符，用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)
