5、最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd” 输出: “bb”
方法一：中心扩散法
中心扩散法的想法很简单：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。要注意一个细节：回文串的长度可能是奇数，也可能是偶数。
1、如果传入重合的索引编码，进行中心扩散，此时得到的最长回文子串的长度是奇数；
2、如果传入相邻的索引编码，进行中心扩散，此时得到的最长回文子串的长度是偶数。
复杂度分析：
时间复杂度：O(N2)O(N^{2})O(N2)。 空间复杂度：O(1)O(1)O(1)。代码：
class Solution: def longestPalindrome(self, s: str) -> str: size = len(s) if size == 0: return '' longest_palindrome = 1 longest_palindrome_str = s[0] for i in range(size): palindrome_odd,odd_len = self._ceter_spread(s,size,i,i) palindrome_even,even_len = self._ceter_spread(s,size,i,i+1) cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even if len(cur_max_sub) > longest_palindrome: longest_palindrome = len(cur_max_sub) longest_palindrome_str = cur_max_sub return longest_palindrome_str def _ceter_spread(self,s,size,left,right): l = left r = right while l >= 0 and r < size and s[l] == s[r]: l -= 1 r += 1 return s[l+1:r],r-l-1解法二：动态规划
解决这类 “最优子结构” 问题，可以考虑使用 “动态规划”：
1、定义 “状态”； 2、找到 “状态转移方程”。
记号说明： 下文中，使用记号 s[l, r] 表示原始字符串的一个子串，l、r 分别是区间的左右边界的索引值，使用左闭、右闭区间表示左右边界可以取到。举个例子，当 s = ‘babad’ 时，s[0, 1] = ‘ba’ ，s[2, 4] = ‘bad’。
1、定义 “状态”，这里 “状态”数组是二维数组。
dp[l][r] 表示子串 s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。即如果子串 s[l, r] 是回文串，那么 dp[l][r] = true。
2、找到 “状态转移方程”。
首先，我们很清楚一个事实：
1、当子串只包含 111 个字符，它一定是回文子串； 2、当子串包含 2 个以上字符的时候：如果 s[l, r] 是一个回文串，例如 “abccba”，那么这个回文串两边各往里面收缩一个字符（如果可以的话）的子串 s[l + 1, r - 1] 也一定是回文串，即：如果 dp[l][r] == true 成立，一定有 dp[l + 1][r - 1] = true 成立。根据这一点，我们可以知道，给出一个子串 s[l, r] ，如果 s[l] != s[r]，那么这个子串就一定不是回文串。如果 s[l] == s[r] 成立，就接着判断 s[l + 1] 与 s[r - 1]，这很像中心扩散法的逆方法。
事实上，当 s[l] == s[r] 成立的时候，dp[l][r] 的值由 dp[l + 1][r - l] 决定，这一点也不难思考：当左右边界字符串相等的时候，整个字符串是否是回文就完全由“原字符串去掉左右边界”的子串是否回文决定。但是这里还需要再多考虑一点点：“原字符串去掉左右边界”的子串的边界情况。
1、当原字符串的元素个数为 333 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 111 个字符，它一定是回文串，故原字符串也一定是回文串； 2、当原字符串的元素个数为 222 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 000 个字符，显然原字符串也一定是回文串。把上面两点归纳一下，只要 s[l + 1, r - 1] 至少包含两个元素，就有必要继续做判断，否则直接根据左右边界是否相等就能得到原字符串的回文性。而“s[l + 1, r - 1] 至少包含两个元素”等价于 l + 1 < r - 1，整理得 l - r < -2，或者 r - l > 2。
综上，如果一个字符串的左右边界相等，以下二者之一成立即可： 1、去掉左右边界以后的字符串不构成区间，即“ s[l + 1, r - 1] 至少包含两个元素”的反面，即 l - r >= -2，或者 r - l <= 2； 2、去掉左右边界以后的字符串是回文串，具体说，它的回文性决定了原字符串的回文性。
于是整理成“状态转移方程”：
dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))
或者
dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))
编码实现细节：因为要构成子串 l 一定小于等于 r ，我们只关心 “状态”数组“上三角”的那部分取值。理解上面的“状态转移方程”中的 (r - l <= 2 or dp[l + 1, r - 1]) 这部分是关键，因为 or 是短路运算，因此，如果收缩以后不构成区间，那么就没有必要看继续 dp[l + 1, r - 1] 的取值。
作者：liweiwei1419 链接：https://leetcode-cn.com/problems/two-sum/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution: def longestPalindrome(self, s: str) -> str: ''' size = len(s) if size == 0: return '' longest_palindrome = 1 longest_palindrome_str = s[0] for i in range(size): palindrome_odd,odd_len = self._ceter_spread(s,size,i,i) palindrome_even,even_len = self._ceter_spread(s,size,i,i+1) cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even if len(cur_max_sub) > longest_palindrome: longest_palindrome = len(cur_max_sub) longest_palindrome_str = cur_max_sub return longest_palindrome_str def _ceter_spread(self,s,size,left,right): l = left r = right while l >= 0 and r < size and s[l] == s[r]: l -= 1 r += 1 return s[l+1:r],r-l-1 ''' size = len(s) if size <= 1 : return s dp = [[False for _ in range(size)] for _ in range(size)] longest_l = 1 res = s[0] for r in range(1,size): for l in range(r): if s[l] == s[r] and (r-l <= 2 or dp[l+1][r-1]): dp[l][r] = True cur_l = r - l + 1 if cur_l > longest_l: longest_l = cur_l res = s[l:r+1] return res复杂度分析：
时间复杂度：O(N2)O(N^{2})O(N2)。 空间复杂度：O(N2)O(N^{2})O(N2)，二维 dp 问题，一个状态得用二维有序数对表示，因此空间复杂度是 O(N2)O(N^{2})O(N2)。