647. 回文子串

解题思路一：中心扩展法（推荐）

回文串的特点是“关于中心对称”。我们可以枚举每一个可能的回文中心，然后向两边扩展，统计所有合法的回文子串。

关键观察：

• 长度为 n 的字符串，共有 2n - 1 个回文中心：
  • n 个单字符中心（对应奇数长度回文，如 "aba"）
  • n - 1 个双字符中心（对应偶数长度回文，如 "abba"）

算法步骤：

1. 遍历每个可能的中心位置
2. 对每个中心，向左右扩展，只要 s[left] == s[right]，就发现一个新的回文子串，计数 +1
3. 继续扩展直到越界或字符不等

Java 实现（中心扩展）

public class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            // 奇数长度：以 i 为中心
            count += expandAroundCenter(s, i, i);
            // 偶数长度：以 i 和 i+1 为中心
            count += expandAroundCenter(s, i, i + 1);
        }
        
        return count;
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

解题思路二：动态规划

也可以用动态规划解决：

• 定义 dp[i][j] 表示子串 s[i..j] 是否为回文
• 状态转移：
  • 如果 s[i] == s[j]：
    • 当 j - i <= 2（即长度 ≤ 3），直接为回文
    • 否则 dp[i][j] = dp[i+1][j-1]
• 每次 dp[i][j] == true 时，计数 +1

Java 实现（DP）

public class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        
        // 注意：i 从后往前，j 从 i 开始往后
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

复杂度分析

✅ 推荐使用中心扩展法：空间更优，代码简洁，效率高。