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-i1){dp[i][j]true;// a 或 aa}else{dp[i][j]dp[i1][j-1];// 依赖内部}}✅ 外层字符相等✅ 内部仍是回文✅ 整体才是回文三、遍历顺序关键因为dp[i][j]依赖dp[i1][j-1]维度顺序i从大到小j从小到大for(intilen-1;i0;i--)for(intji;jlen;j)✅ 保证子问题先计算完成✅ AC 代码Java基于你的代码classSolution{publicintcountSubstrings(Strings){intres0;char[]sss.toCharArray();intlens.length();boolean[][]dpnewboolean[len][len];for(intilen-1;i0;i--){for(intji;jlen;j){if(ss[i]ss[j]){if(j-i1){dp[i][j]true;res;}elseif(dp[i1][j-1]){dp[i][j]true;res;}}}}returnres;}}⏱️ 复杂度分析指标复杂度时间复杂度O(n²)空间复杂度O(n²) 与其他解法的对比解法时间复杂度空间复杂度特点中心扩展O(n²)O(1)面试最爱DP本题O(n²)O(n²)易理解ManacherO(n)O(n)偏竞赛✅ 一句话总结区间 DP两端相等且内部是回文则整体是回文。 面试加分点建议记住✅ 为什么i要从大到小✅ 为什么j - i 1要单独判断✅ DP 与中心扩展的本质联系✅ 如何优化到 O(1) 空间
回文子串（Palindromic Substrings）—— 题解
发布时间：2026/6/10 23:23:22
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-i1){dp[i][j]true;// a 或 aa}else{dp[i][j]dp[i1][j-1];// 依赖内部}}✅ 外层字符相等✅ 内部仍是回文✅ 整体才是回文三、遍历顺序关键因为dp[i][j]依赖dp[i1][j-1]维度顺序i从大到小j从小到大for(intilen-1;i0;i--)for(intji;jlen;j)✅ 保证子问题先计算完成✅ AC 代码Java基于你的代码classSolution{publicintcountSubstrings(Strings){intres0;char[]sss.toCharArray();intlens.length();boolean[][]dpnewboolean[len][len];for(intilen-1;i0;i--){for(intji;jlen;j){if(ss[i]ss[j]){if(j-i1){dp[i][j]true;res;}elseif(dp[i1][j-1]){dp[i][j]true;res;}}}}returnres;}}⏱️ 复杂度分析指标复杂度时间复杂度O(n²)空间复杂度O(n²) 与其他解法的对比解法时间复杂度空间复杂度特点中心扩展O(n²)O(1)面试最爱DP本题O(n²)O(n²)易理解ManacherO(n)O(n)偏竞赛✅ 一句话总结区间 DP两端相等且内部是回文则整体是回文。 面试加分点建议记住✅ 为什么i要从大到小✅ 为什么j - i 1要单独判断✅ DP 与中心扩展的本质联系✅ 如何优化到 O(1) 空间
)
