LeetCode 第 647 题：回文子串（Palindromic Substrings）

题目描述

给你一个字符串 s，请你统计并返回这个字符串中 回文子串 的数量。
回文子串是指正着读和反着读都一样的连续子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串："a", "b", "c"

示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串："a", "a", "a", "aa", "aa", "aaa"

解题思路

1. 暴力解法（不可取）

最直观的方法是枚举所有可能的子串（起点和终点），然后检查每个子串是否为回文。

• 子串数量：O(n²)
• 检查回文：O(n)
  总时间复杂度 O(n³)，在较大输入下会超时。

2. 中心扩展法（核心解法）

关键观察：回文串具有对称性。我们可以从每个可能的“中心”向两边扩展，判断能形成多少回文子串。

中心点的选择：

• 奇数长度回文：中心是一个字符（如 "aba" 的中心是 'b'）
• 偶数长度回文：中心是两个字符之间的“空隙”（如 "abba" 的中心在两个 'b' 之间）

因此，对于长度为 n 的字符串，有 2n-1 个可能的中心（n 个字符位置 + n-1 个空隙）。

步骤：

1. 遍历每个中心点（从 0 到 2n-2）
2. 对于每个中心，设置左右指针：
   • 若中心是字符（索引 i），则 left = i, right = i
   • 若中心是空隙（索引 i 和 i+1 之间），则 left = i, right = i+1
3. 左右指针向两边扩展，若 s[left] == s[right]，则找到一个回文子串，计数加一，继续扩展；否则停止。

时间复杂度：O(n²)
空间复杂度：O(1)

3. 动态规划法（拓展思路）

定义 dp[i][j] 表示子串 s[i..j] 是否为回文。
状态转移方程：

• 如果 s[i] == s[j] 且 (j - i <= 2 或 dp[i+1][j-1] 为真)，则 dp[i][j] = true
• 否则 dp[i][j] = false

初始化后，遍历所有 i≤j 的情况，统计为真的个数。
时间复杂度 O(n²)，空间复杂度 O(n²)。

详细步骤（以中心扩展法为例）

以 s = "aaa" 为例：

1. 中心点 0（字符 'a'）：

   • left=0, right=0 → "a" 是回文，计数=1
   • 扩展：left=-1（越界）→ 停止

2. 中心点 1（字符 'a' 和 'a' 之间的空隙）：

   • left=0, right=1 → "aa" 是回文，计数=2
   • 扩展：left=-1 → 停止

3. 中心点 2（字符 'a'）：

   • left=1, right=1 → "a" 是回文，计数=3
   • 扩展：left=0, right=2 → "aaa" 是回文，计数=4
   • 扩展：left=-1 → 停止

4. 中心点 3（字符 'a' 和 'a' 之间的空隙）：

   • left=1, right=2 → "aa" 是回文，计数=5
   • 扩展：left=0, right=3（越界）→ 停止

5. 中心点 4（字符 'a'）：

   • left=2, right=2 → "a" 是回文，计数=6
   • 扩展：left=1, right=3（越界）→ 停止

最终计数为 6，与示例一致。

代码实现（中心扩展法）

def countSubstrings(s: str) -> int:
    n = len(s)
    count = 0
    
    for center in range(2 * n - 1):
        left = center // 2
        right = left + center % 2
        
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    return count

总结

中心扩展法利用了回文串的对称性质，通过枚举所有可能的中心并向外扩展，高效地统计回文子串数量。这种方法比暴力法优化了一个数量级，且代码简洁易懂。