面试题库 › 客户端 › 统计回文子串的数目

统计回文子串的数目

难度 ★★☆在 1 场真实面经中被问到 方向:客户端考点:动态规划

哪些公司问过

快手1

常见岗位:客户端

答案要点

  1. 中心扩展:共 2n-1 个中心,向两边扩展,每次扩展成功计数加一
  2. 统一写法:中心 i 从 0 到 2n-2,左端 i/2,右端 i/2 + i%2
  3. 时间 O(n²),空间 O(1)
  4. DP:dp[i][j] = s[i]==s[j] 且 (j-i<2 或 dp[i+1][j-1]),i 从后往前
  5. Manacher 算法可做到 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题