最长回文子串（Longest Palindromic Substring） 题目描述： 给定一个字符串 s ，找到 s 中最长的回文子串。回文串是正着读和反着读都相同的字符串。例如，字符串 "babad" 的最长回文子串可能是 "bab" 或 "aba" 。 解题思路 1. 理解回文串的特性 回文串具有对称性。例如： 奇数长度回文（如 "aba" ）：以中心字符对称。 偶数长度回文（如 "abba" ）：以中心两个字符之间的空隙对称。 2. 暴力解法（不可行） 直接枚举所有子串（共 \(O(n^2)\) 个），检查每个子串是否为回文（\(O(n)\)），总时间复杂度为 \(O(n^3)\)，在较长字符串下会超时。 3. 中心扩展法（最优解之一） 核心思想 ： 遍历字符串的每个位置，尝试以该位置（或空隙）为中心，向两边扩展，找到以该中心为起点的最长回文子串。 步骤 ： 遍历字符串的每个索引 i （从 0 到 n-1 ）： 情况1（奇数长度） ：以 s[i] 为中心，向左右扩展。 情况2（偶数长度） ：以 s[i] 和 s[i+1] 之间的空隙为中心，向左右扩展。 对每个中心，用双指针 left 和 right 向两边移动，直到字符不相等为止。 记录当前回文串的起始位置和长度，更新最长回文子串。 举例 （以 s = "babad" 为例）： i=0 ：奇数扩展得 "b" ，偶数扩展得 "" （因为 "b"≠"a" ）。 i=1 ：奇数扩展以 "a" 为中心，得到 "bab" （左右扩展至 s[0]='b' 和 s[2]='b' ）；偶数扩展以 "a" 和 "b" 之间为中心，失败。 继续遍历，最终找到最长回文 "bab" 或 "aba" 。 代码关键点 ： 编写辅助函数 expand(l, r) ，从 (l, r) 向两边扩展。 注意边界条件（ l ≥ 0 , r < n ）。 4. 动态规划法（补充思路） 定义 dp[i][j] 表示子串 s[i..j] 是否为回文。 状态转移方程 ： 如果 s[i] == s[j] 且 (j-i ≤ 2 或 dp[i+1][j-1] = true) ，则 dp[i][j] = true 。 时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n^2)\)，不如中心扩展法简洁。 总结 中心扩展法 是本题最直观且高效的方法，时间复杂度 \(O(n^2)\)，空间复杂度 \(O(1)\)。 关键点：正确处理奇偶回文，避免重复计算。