最长回文子串
题目来源：https://leetcode-cn.com/problems/longest-palindromic-substring/
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解题思路
- 动态规划；
- 如果是单字符，一定是回文；
- 如果字符串的首尾字符不相同，则一定不是回文；若是首尾相同，则继续判断内部子串；
- 关于内部子串，要考虑边界的问题。
s[i]和s[j]若为相同字符，去掉首尾s[i]和s[j]，需往下判断。[i + 1, j - 1]这个区间，需要注意有可能无法构成区间，也就是长度小于 2 的时候。转换成公式就是：j-1-(i+1)+1<2可得j-i<3。这里也就表示s[i, j]长度为 2 或 3 的时候只需要判断首尾字符相同就可以下结论。 - 根据上面得到的
j-i<3即可判断结果展开说下：
a. 若s[i+1, j-1]区间只有 1 个字符，符合单字符就是回文的规则，直接确定结论
b. 若s[i+1, j-1]为空，那么子串s[i, j]则是回文子串。
代码实现
class Solution:
def longestPalindrome(self, s: str) -> str:
length = len(s)
# 如果字符串长度小于 2，直接返回，单字符是回文
if length < 2:
return s
# 最长子串长度，至少为 1，单字符是回文
max_sub_len = 1
# 最长子串开始位置
start = 0
# 动态规划
dp = [[False for _ in range(length)] for _ in range(length)]
# 单字符是回文，将矩阵对角线设置为 True
for i in range(length):
dp[i][i] = True
# 遍历字符串，对比子串头尾是否相同
# 相同则继续对比内部子串
# 子串首尾字符相同且子串长度为 2 或者为 3 时，可以直接判定为回文子串
for j in range(1, length):
for i in range(0, j):
# 首尾字符相同，继续比较
if s[i] == s[j]:
# 首尾相同，子串长度小于等于 3，可以直接下结论
if j - i < 3:
dp[i][j] = True
else: # 否则继续比较内部子串
dp[i][j] = dp[i+1][j-1]
else:
continue
if dp[i][j]:
# 获取此时的回文子串长度
cur_sub_len = j - i + 1
if cur_sub_len > max_sub_len:
max_sub_len = cur_sub_len
# 重置子串开始位置
start = i
return s[start:start + max_sub_len]
实现效果
结果展示
以上就是本篇的主要内容，虽然跑出来的结果不太理想，但是该题中动态规划的大概思想就是这样，后续考虑改进方法实现该问题。
欢迎关注微信公众号《书所集录》
