LeetCode-5. 最长回文子串

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解题思路：动态规划。令dp[i][j]表示s[i:j+1]是否为回文子串，则dp[i][j] = s[i] == s[j] and (j -i <=2 or dp[i+1][j-1])。若dp[i][j]为真，则计算回文子串长度，若回文子串长度大于longest，则更新longest，start，end。注意dp数组的更新方向是从下到上，从左到右。

Python3代码如下：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[False]*len(s) for i in range(len(s))]
        start,end,longest = -1,-1,1
        for i in reversed(range(len(s))):
            for j in range(i,len(s)):
                if s[i] == s[j] and (j-i<=2 or dp[i+1][j-1]):
                    dp[i][j] = True
                    if j-i+1 >= longest:
                        longest = j-i+1
                        start = i
                        end = j
        return s[start:end+1]