指定字符串s，在s中找到最长的回文子串。s的最大长度可以假定为1000。
示例 1：
输入： 'babad '输出： 'bab '也是有效的答案。示例 2：
输入： 'cbbd '输出： 'bb' 解题思路
首先最简单的是暴力解法，用双重循环决定子串的范围，然后判断子串是否是回文，最后返回最长的回文子串。
class解决方案3360 deflongestpalindrome (self，s ) : ' ' : types : str : rtype : str ' ' max _ len，result ' ' len ) s )1) :ifs(I:j )=s[I:j][3360:-1]这个问题可以通过动态规划来解决，函数f(I，j ) f，j ) I，j
f(I，j )=f ) I1，j1 ) s i=s j时f(I，j )=f ) I1，j-1 ) ( s_i=s_j时f ) I，j )=f ) I1，j1 )时si=
i + 1 j=i+1 j=i+1的时候，此时字符串由两个相同字符构成；当 i = j i=j i=j的时候，此时字符串由单个字符构成。 class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if not s: return "" s_len = len(s) mem = [[0]*s_len for _ in range(s_len)] left, right, result_len = 0, 0, 0 for j in range(s_len): for i in range(j): if s[i] == s[j] and (j-i < 2 or mem[i+1][j-1]): mem[i][j] = 1 if mem[i][j] and result_len < j-i+1: result_len = j - i + 1 left, right = i, j mem[j][j] = 1 return s[left:right+1]这种算法的时间复杂度是O(n^2)，空间复杂度也是O(n^2)。有没有更好的做法呢？
我们知道回文串是中心对称的，所以只要找到回文串的中心，然后向两边扩展即可。这里的中心位置我们要奇偶分开考虑，如果字符串长度是奇数的话，中心就只有一个元素；如果字符串是偶数的话，那么中心是两个元素。
class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if not s or len(s) < 1: return "" def expandAroundCenter(left, right): L, R = left, right while L >= 0 and R <len(s) and s[L] == s[R]: L -= 1 R += 1 return R - L - 1 left, right = 0, 0 for i in range(len(s)): len1 = expandAroundCenter(i, i) # 奇数 len2 = expandAroundCenter(i, i+1) # 偶数 max_len = max(len1, len2) if max_len > right - left: left = i - (max_len - 1)//2 right = i + max_len//2 return s[left:right+1]还有一种思路也非常不错，可以先确定回文串的右边界i，然后以右边界i向左找回文串。假设在i之前的最长回文子串长度是l，此时我们需要分别检查i+1左侧字符串长度为l+2和l+1子串是不是回文串。如果l+2是回文串，那么字符串的最大长度变成l+2，对于l+1同理。
代码如下：
class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) < 2 or s == s[::-1]: return s start, maxlength = 0, 1 for i in range(1, len(s)): odd = s[i-maxlength-1:i+1] # 检查l+2 even = s[i-maxlength:i+1] # 检查l+1 if i-maxlength-1 >= 0 and odd == odd[::-1]: start = i-maxlength-1 maxlength += 2 elif i-maxlength >= 0 and even == even[::-1]: start = i-maxlength maxlength += 1 return s[start:start+maxlength]通过maxlength我们过滤了许多不必要的重复计算，所以这个代码的效率比前面一个要快许多。
这样我们的空间复杂度就优化到了常数级别。有没有更快的算法呢？有，使用Manacher算法，类似的思想在KMP算法中也有应用。
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！