摘要：“如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。”

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

“如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。”

输入：s = "babad"

输出："bab"

中心扩展算法

思路：回文字符串有两种类型，比如 aba 或者 abbc。

第一种是一个中心点往两边扩展；

第二种是两个中心点往两边扩展；

遍历中心点，使用双指针往两边扩展，如果两边的字母相同，就可以继续扩展；如果两边的字母不同，就停止扩展，取两种情况的最大子串

参考程序（kidscode.cn）：

如果有兴趣可以尝试动态规划的方法，仅提供思路。

动态规划

思路：使用动态规划算法解题步骤

定义状态：

我们可以定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文串。

初始化状态：

将所有长度为 1 的子串都初始化为回文，即 dp[i][i] = true。

检查所有长度为 2 的子串，如果两个字符相等，将 dp[i][i+1] 设为 true。

状态转移方程：

对于长度大于 2 的子串，dp[i][j] 是否为回文串取决于 dp[i+1][j-1] 和 s[i] == s[j]。

即dp[i][j] = dp[i+1][j-1] && s[i] == s[j]。

处理边界条件：

在上述初始化中已经处理了长度为 1 和 2 的情况。

自底向上构建解：

通过两层嵌套循环，自底向上地填充 dp 数组，从小规模子问题逐步构建到整个问题。

记录最优解：

在状态转移的过程中，不断更新记录最长回文子串的起始索引和长度。

返回结果：

最终，通过起始索引和长度，可以得到最长回文子串

原文少儿编程网（kidscode.cn）

来源：营口口偶雨