面试题库 › Java 后端 › 单词拆分(LeetCode 139)动态规划

单词拆分(LeetCode 139)动态规划

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

哪些公司问过

阿里巴巴1百度1

常见岗位:AI 应用 / Agent 开发、推荐搜索广告

答案要点

  1. 状态 dp[i]:前 i 个字符能否拆分;初始 dp[0] = true
  2. 转移:存在 j < i,dp[j] 为真且 s[j:i] 在字典中,则 dp[i] 为真
  3. 字典用哈希集合;时间 O(n²) 次查询,空间 O(n)
  4. 优化:只枚举长度不超过最长单词的 j,或用 Trie 匹配
  5. 字典单词可重复使用;变体 LC140 需输出所有拆分方案

易错点

面试官常见追问

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

相关面试题