回文子串（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]：
| 维度 | 顺序 |
|---|---|
| i | 从大到小 |
| j | 从小到大 |
for(inti=len-1;i>=0;i--)for(intj=i;j<len;j++)✅ 保证子问题先计算完成
✅ AC 代码（Java，基于你的代码）
classSolution{publicintcountSubstrings(Strings){intres=0;char[]ss=s.toCharArray();intlen=s.length();boolean[][]dp=newboolean[len][len];for(inti=len-1;i>=0;i--){for(intj=i;j<len;j++){if(ss[i]==ss[j]){if(j-i<=1){dp[i][j]=true;res++;}elseif(dp[i+1][j-1]){dp[i][j]=true;res++;}}}}returnres;}}⏱️ 复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n²) |
🔍 与其他解法的对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 中心扩展 | O(n²) | O(1) | 面试最爱 |
| DP（本题） | O(n²) | O(n²) | 易理解 |
| Manacher | O(n) | O(n) | 偏竞赛 |
✅ 一句话总结
区间 DP：两端相等且内部是回文，则整体是回文。
📌 面试加分点（建议记住）
- ✅ 为什么
i要从大到小？ - ✅ 为什么
j - i <= 1要单独判断？ - ✅ DP 与中心扩展的本质联系
- ✅ 如何优化到 O(1) 空间？