给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
暴力解法：
class Solution: def longestPalindrome(self, s): # 暴力解法 n = len(s) # s为空的情况 if n == 0: return s # 记录回文串的起始位置 start = 0 # 记录回文串的长度 maxlength = 0 # i 代表起始地址 for i in range(n): # j 代表终止地址 for j in range(i+1, n): tmp1 = i tmp2 = j # 判断是否为回文串 while tmp1 < tmp2 and s[tmp1]==s[tmp2]: tmp1 += 1 tmp2 -= 1 # 当满足回文串且长度更长时，记录起始位置和长度 if tmp2 <= tmp1 and j-i+1>maxlength: maxlength = j - i + 1 start = i if maxlength > 0: return s[start: start+maxlength] return s[start]
DP
1、dp[i][j]数组：表示区间范围[i,j] （左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
2、递推：dp[i][j] 是回文，那么只有当s[i] == s[j] 时，dp[i+1][j-1] = true（是回文串）。当对于长度为 1 的子串，显然是个回文串；对于长度为 2 的子串，只要两个字母相同，就是一个回文串。
3、dp数组初始化：全为False
4、遍历顺序：
a、以矩阵来看，如果是从上到下，从左到右遍历（顺序遍历），那么会用到没有计算过dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断[i,j]是不是回文，那结果一定是不对的。所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
b、以动态子串：动态规划的边界条件就是子串长度为1或2，从长度较短的字符串向长度较长的字符串进行转移的，dp[i + 1][j - 1]为较短的子串，可以使用，枚举子串长度即可。
if s[i] == s[j]: if j - i <= 1: # 子串长度为1或2 dp[i][j] = True elif dp[i+1][j-1]: dp[i][j] = True if dp[i][j] and j - i > r - l: # dp[i][j] 是回文，记录边界 l, r = i, j
"""a、矩阵""" def dp(s): lenth = len(s) l, r= 0, 0 dp = [[False] * lenth for i in range(lenth)] for i in range(lenth - 1, -1,-1): for j in range(i,lenth): if s[i] == s[j]: if j - i <= 1: dp[i][j] = True elif dp[i+1][j-1]: dp[i][j] = True if dp[i][j] and j - i > r - l: l, r = i, j return s[l:r+1] """b、子串长度""" def dp(s: str) -> str: n = len(s) if n < 2: return s max_len = 1 begin = 0 # dp[i][j] 表示 s[i..j] 是否是回文串 dp = [[False] * n for _ in range(n)] for i in range(n): dp[i][i] = True # 递推开始 # 先枚举子串长度 for L in range(2, n + 1): # 枚举左边界，左边界的上限设置可以宽松一些 for i in range(n): # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得 j = L + i - 1 # 如果右边界越界，就可以退出当前循环 if j >= n: break if s[i] != s[j]: dp[i][j] = False else: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] # 只要 dp[i][L] 是回文，记录回文长度和起始位置 if dp[i][j] and j - i + 1 > max_len: max_len = j - i + 1 begin = i return s[begin:begin + max_len]
中心扩散
如果两边的字母相同，就可以继续扩展；如果两边的字母不同，就停止扩展
class Solution: def longestPalindrome(self,s): start, end = 0, 0 for i in range(len(s)): l1, r1 = self.expandAroundCenter(s, i, i) # 中心为奇数 b a b l2, r2 = self.expandAroundCenter(s, i, i + 1) # 中心为偶数 b aa b if r1 - l1 > end - start: start, end = l1, r1 if r2 - l2 > end - start: start, end = l2, r2 return s[start:end + 1] def expandAroundCenter(self,s, l, r): while l >= 0 and r < len(s) and s[l] == s[r]: # 字母相同，继续扩展 l -= 1 r += 1 return l + 1, r - 1 # 返回下标 if __name__ == '__main__': s = "babad" sl = Solution() print(s.longestPalindrome(s))
参考：
链接：https://leetcode.cn/problems/longest-palindromic-substring
链接：https://blog.csdn.net/qq_43325582/article/details/122671430
