给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd" 输出: "bb"
动态规划：
class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""n = len(s)dp = [[False] * n for _ in range(n)]longest = ''for l in range(n):for i in range(n):j = i + lif j > n-1:breakif l == 0:dp[i][j] = Trueelif l == 1:dp[i][j] = s[i] == s[j]else:dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])if dp[i][j] and l + 1 > len(longest):longest = s[i:j+1]return longest
对于字符串"aba"而言，因为它是回文串，那么"babab"也一定是回文串，因为它们中间是个回文串，且首尾字符相同。根据这样的思想我们可以用动态规划来解题。
我们用 P(i,j) 来表示字符串 s 的第 i 个位置到第 j 个位置组成的字符串是否为回文串。P(i,j) = True表示是回文串， False表示不是。
那么我们可以很容易的推导出状态转移方程：
然后我们需要讨论一下边界情况，就是字串长度为1或者2。如果长度为1那么它显然就是一个回文串，而如果长度为2那么只要两个字符相等即可。
至此我们就完成来动态规划的部分，现在问题是如何遍历出所有的子串。我们可以另两端点的距离（串长-1）分别从0到n-1遍历，然后遍历选择每个起点就能完成整个步骤。
中心扩展算法：
class Solution:def expandAroundCenter(self, s, left, right):while left >= 0 and right < len(s) and s[left] == s[right]:left -= 1right += 1return left + 1, right - 1def longestPalindrome(self, s: str) -> str:start, end = 0, 0for i in range(len(s)):left1, right1 = self.expandAroundCenter(s, i, i)left2, right2 = self.expandAroundCenter(s, i, i + 1)if right1 - left1 > end - start:start, end = left1, right1if right2 - left2 > end - start:start, end = left2, right2return s[start: end + 1]
其实我们也可以从边界条件开始出发思考问题。我们可以先找到该字符串所有的回文串中心，然后向两边开始扩张。比如s[i] 只有一个字符，那么它必然是个回文串，然后我们向两边扩散，去判断s[i-1,i+1]是否为回文串。对于回文串来讲边界情况有两种，一种长度为1那么它必为回文串，另一种长度为2，那么如果两个字符相等则为回文串。我们找到所有的回文串中心，然后开始向两边扩张，直到新子串的首尾不相同，即找到对于这个回文中心最长的长度。