统计回文子串的数目
哪些公司问过
答案要点
- 中心扩展:共 2n-1 个中心,向两边扩展,每次扩展成功计数加一
- 统一写法:中心 i 从 0 到 2n-2,左端 i/2,右端 i/2 + i%2
- 时间 O(n²),空间 O(1)
- DP:dp[i][j] = s[i]==s[j] 且 (j-i<2 或 dp[i+1][j-1]),i 从后往前
- Manacher 算法可做到 O(n)
易错点
- 只考虑奇数长度的中心,漏掉偶数长度回文
- DP 遍历顺序错误,用到未计算的状态
- 把相同内容不同位置的回文子串只计一次,题目要求按位置计数
面试官常见追问
- DP 为什么 i 要从后往前遍历?
- 如果要求最长回文子串呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场