LeetCode 第 647 题：回文子串（Palindromic Substrings） 题目描述 给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。回文子串是指正着读和反着读都一样的连续子串。具有不同起始位置或结束位置的子串，即使由相同的字符组成，也会被视作不同的子串。 示例 输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c" 输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 解题思路 要统计所有回文子串，最直观的方法是枚举所有可能的子串，并检查它们是否是回文。但这种方法的时间复杂度为 O(n³)，对于较长的字符串效率极低。我们需要一种更高效的方法。 核心观察 一个回文串去掉首尾两个字符后，剩下的部分仍然是回文串（如果存在）。例如，"abba" 去掉首尾的 'a' 后，"bb" 仍然是回文串。这个性质意味着我们可以利用动态规划或中心扩展法来避免重复计算。 方法一：中心扩展法（推荐） 回文串可以分为奇数和偶数长度两种情况。我们可以遍历字符串，以每个字符（或每两个相邻字符）作为“中心”，向两边扩展，判断能形成多少个回文子串。 步骤分解 初始化计数器 ： count = 0 ，用于累计回文子串的数量。 遍历所有中心点 ：字符串中可能的中心点有 2n - 1 个。其中 n 个是单个字符（作为奇数长度回文串的中心）， n-1 个是两个相邻字符的中间位置（作为偶数长度回文串的中心）。 定义扩展函数 ：编写一个辅助函数 expandAroundCenter ，它接收字符串 s 、左指针 left 和右指针 right 。 只要 left 和 right 在字符串边界内，并且 s[left] 等于 s[right] ，就说明当前子串是回文。 计数器 count 加 1。 然后将 left 向左移动一位， right 向右移动一位，继续检查更长的子串。 遍历中心点 ： 奇数长度中心 ：对于每个索引 i ，调用 expandAroundCenter(s, i, i) 。此时中心是一个字符。 偶数长度中心 ：对于每个索引 i ，调用 expandAroundCenter(s, i, i+1) 。此时中心是两个字符的间隙。 返回结果 ：遍历完成后， count 即为所有回文子串的数量。 复杂度分析 时间复杂度：O(n²)。遍历中心点需要 O(n) 的时间，每个中心点最多扩展 O(n) 次。 空间复杂度：O(1)。只使用了常数级别的额外空间。 方法二：动态规划 我们也可以用一个二维 DP 数组 dp[i][j] 来记录子串 s[i..j] 是否为回文串。 步骤分解 定义状态 ： dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否是回文串。 初始化 ：所有长度为 1 的子串都是回文串，即 dp[i][i] = true 。 状态转移方程 ： 如果 s[i] == s[j] ，那么子串 s[i..j] 是否是回文取决于其内部子串 s[i+1..j-1] 是否是回文。 即 dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1]) 。 解释：如果 j - i <= 2 （即子串长度为 2 或 3），只要首尾字符相等，它一定是回文串（例如 "aa" 或 "aba"）。如果长度大于 3，就需要看内部子串。 遍历顺序 ：由于 dp[i][j] 依赖于 dp[i+1][j-1] （即左下方的值），我们需要从下到上、从左到右遍历。或者按照子串长度 L 从 2 到 n 进行遍历。 统计结果 ：在填充 DP 表的过程中，每当 dp[i][j] 为 true 时，就将计数器加一。 复杂度分析 时间复杂度：O(n²)。需要填充一个 n x n 的表格。 空间复杂度：O(n²)。需要维护一个 n x n 的 DP 表。 总结 中心扩展法因其简洁性和优秀的空间复杂度（O(1)）通常是本题的首选。动态规划方法思路清晰，是理解回文类问题的经典范式，但空间复杂度较高。两种方法都有效地将复杂度从 O(n³) 优化到了 O(n²)。