回文子串（Palindromic Substrings）—— 题解

LeetCode 647：回文子串（Palindromic Substrings）—— 题解 ✅

🔗 题目链接

👉 https://leetcode.cn/problems/palindromic-substrings/

📖 内容概要

给定一个字符串 s，统计并返回 这个字符串中回文子串的数目。
子串是连续的，回文指正读和反读相同。

✅ 区间 DP
✅ 中心扩展思想的 DP 实现
✅ 面试高频题

💡 解题思路（核心）

一、状态定义

dp[i][j] = s[i...j] 是否是回文子串

二、状态转移方程（最重要）

if (s[i] == s[j]) {
if (j – i <= 1) {
dp[i][j] = true; // "a" 或 "aa"
} else {
dp[i][j] = dp[i+1][j–1]; // 依赖内部
}
}

✅ 外层字符相等
✅ 内部仍是回文
✅ 整体才是回文

三、遍历顺序（关键）

因为 dp[i][j] 依赖 dp[i+1][j-1]：

for (int i = len – 1; i >= 0; i—)
for (int j = i; j < len; j++)

✅ 保证子问题先计算完成

✅ AC 代码（Java，基于你的代码）

class Solution {
public int countSubstrings(String s) {
int res = 0;
char[] ss = s.toCharArray();
int len = s.length();

boolean[][] dp = new boolean[len][len];

for (int i = len – 1; i >= 0; i—) {
for (int j = i; j < len; j++) {
if (ss[i] == ss[j]) {
if (j – i <= 1) {
dp[i][j] = true;
res++;
} else if (dp[i + 1][j – 1]) {
dp[i][j] = true;
res++;
}
}
}
}
return res;
}
}

⏱️ 复杂度分析

🔍 与其他解法的对比

✅ 一句话总结

区间 DP：两端相等且内部是回文，则整体是回文。

📌 面试加分点（建议记住）

• ✅ 为什么 i 要从大到小？
• ✅ 为什么 j – i <= 1 要单独判断？
• ✅ DP 与中心扩展的本质联系
• ✅ 如何优化到 O(1) 空间？