给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母（大写和/或小写）组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用动态规划求解。
- 状态定义：g[i][j] 表示字符串 s[i, j+1] 是否为回文串。
- 转移方程：g[i][j] = g[i+1][j-1]（中间是否为回文串） or s[i] == s[j]（两边是否相同） 。
- 返回值：最大的边界 i, j。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
g = [[True]*n for _ in range(n)]
left = right = 0
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
g[i][j] = g[i+1][j-1] and s[i] == s[j]
if g[i][j] and right - left < j - i:
left, right = i, j
return s[left:right+1]
- 时间复杂度 O(n^2)：n 为字符串长度。
- 空间复杂度 O(n^2)：n 为字符串长度。
二解
中心扩展算法。从字符串某一位置开始，向两边扩展（如果两边相同）。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
def expand_around_center(i, j):
while i >= 0 and j < n and s[i] == s[j]:
i -= 1
j += 1
return i + 1, j - 1
left = right = 0
for i in range(n):
# 如果是奇数 aba
l1, r1 = expand_around_center(i, i)
# 如果是偶数 abba
l2, r2 = expand_around_center(i, i+1)
if r1 - l1 > right - left:
left, right = l1, r1
if r2 - l2 > right - left:
left, right = l2, r2
return s[left: right + 1]
- 时间复杂度 O(n^2)：n 为字符串长度。
- 空间复杂度 O(1)。