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

题目描述
给定一个字符串 s，请统计这个字符串中回文子串的总数。
回文子串是指正着读和反着读都一样的连续子串。
具有不同起始位置或结束位置的子串，即使内容相同，也会被视作不同的子串。
例如：

• 输入 "abc"，输出 3（"a"、"b"、"c"）
• 输入 "aaa"，输出 6（"a"、"a"、"a"、"aa"、"aa"、"aaa"）

解题思路
核心思想是枚举所有可能的回文中心，并向两侧扩展。回文串分为奇数和偶数长度两种情况：

1. 奇数长度：回文中心是一个字符（如 "aba" 的中心是 'b'）。
2. 偶数长度：回文中心是两个字符之间的“空隙”（如 "aa" 的中心在两个 'a' 之间）。

步骤分解

1. 遍历所有回文中心：

   • 对于长度为 n 的字符串，共有 2n-1 个回文中心（n 个字符和 n-1 个空隙）。
   • 例如 "abc"：回文中心为 0（字符 'a'）、0.5（'a' 和 'b' 之间）、1（字符 'b'）、1.5、2。

2. 扩展判定回文：

   • 对每个中心，设置左右指针 left 和 right。
     • 奇数中心：left = center, right = center
     • 偶数中心：left = center, right = center + 1
   • 向两侧扩展，若 s[left] == s[right]，则发现一个回文子串，计数器加1，继续扩展；否则停止。

3. 复杂度分析：

   • 时间：O(n^2)（每个中心最多扩展 O(n) 次）
   • 空间：O(1)

具体示例
以 s = "aaa" 为例：

1. 中心 0（奇数）：
   • 扩展：(0,0) -> "a"；(0-1,0+1) 越界停止 → 计数+1
2. 中心 0.5（偶数）：
   • 扩展：(0,1) -> "aa"；(0-1,1+1) 越界停止 → 计数+1
3. 中心 1（奇数）：
   • 扩展：(1,1) -> "a"；(0,2) -> "aaa"；(-1,3) 停止 → 计数+2
4. 中心 1.5（偶数）：
   • 扩展：(1,2) -> "aa"；(0,3) 停止 → 计数+1
5. 中心 2（奇数）：
   • 扩展：(2,2) -> "a"；停止 → 计数+1
     总计：1 + 1 + 2 + 1 + 1 = 6

代码实现（Python）

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

关键点总结

• 统一处理奇偶中心：通过 center 遍历 0 到 2n-2，用 center % 2 区分奇偶。
• 扩展时及时停止：遇到字符不匹配或边界时终止当前中心的扩展。