面试题库 › Go 后端 › 单词拆分:句子能否由单词集合构成

单词拆分:句子能否由单词集合构成

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

哪些公司问过

华为2

常见岗位:Go 后端、Java 后端

答案要点

  1. 单词集合放入哈希集合,O(1) 判断子串是否为单词
  2. dp[i]:前 i 个字符能否被拼出,dp[0] 为真
  3. 转移:存在 j 使 dp[j] 为真且 s[j:i] 在集合中
  4. 用单词最大长度限制 j 的范围剪枝
  5. 字典树可从每个可达位置一次匹配所有单词

易错点

面试官常见追问

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

相关面试题