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)