面试题库 › C++ / 后端 › 单词拆分:判断字符串能否由字典单词拼接

单词拆分:判断字符串能否由字典单词拼接

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

哪些公司问过

字节跳动1微软1

常见岗位:软件开发(未写技术栈)

答案要点

  1. dp[i] 表示前 i 个字符能否拆分,dp[0]=true
  2. dp[i] 为真当且仅当存在 j 使 dp[j] 为真且 s[j..i) 在字典中
  3. 字典放入哈希集合加速查找,找到可行 j 即可跳出
  4. 按最长单词长度限制枚举范围,或用 Trie 从可达位置向后匹配
  5. 单词可重复使用,本质是完全背包式的可达性问题

易错点

面试官常见追问

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

相关面试题