面试题库 › 算法 / 大模型 › 最长回文子串(区间 DP 解法)

最长回文子串(区间 DP 解法)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

小红书1

常见岗位:大模型算法

答案要点

  1. 状态:dp[i][j] 表示 s[i..j] 是否回文
  2. 转移:s[i]==s[j] 且 (j-i<2 或 dp[i+1][j-1])
  3. 遍历顺序:按长度递增,或 i 从后往前、j 从 i 往后,保证子状态已算出
  4. 记录最长区间的起点和长度,最后截取
  5. 复杂度 O(n²) 时间与空间;中心扩展 O(1) 空间,Manacher O(n)

易错点

面试官常见追问

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

相关面试题