解题思路：动态规划

• 使用 dp[i][j] 记录 s[i:j+1] 是否是回文子串。
• 递推关系：
  • 如果 s[i] == s[j]：
    • j - i == 1，即两个字符相等，则是回文。
    • dp[i+1][j-1] == True（内部是回文），则 dp[i][j] = True。
• 遍历 j 作为子串右端点，从小到大枚举 i 作为左端点，更新 dp[i][j] 并记录最长回文子串的起始位置 start 和长度 max_length。
• 时间复杂度 O(n²)，空间复杂度 O(n²)。

Leetcode 93.最长回文子串-原题链接

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。

输入描述

输入包含一个字符串 s（$1 \leq |s| \leq 1000$），仅由数字和英文字母组成。

输出描述

输出一行，表示 s 中最长的回文子串。如果存在多个答案，返回任意一个。

样例输入 1

babad

样例输出 1

bab

说明：aba 也是符合题意的答案。

样例输入 2

cbbd

样例输出 2

bb

提示

• s 仅由 数字 和 英文字母 组成。
• s 至少包含 1 个字符。
• 若存在多个答案，返回 任意一个。