面试题库 › C++ / 后端 › 最长单词:求能由其他单词拼接成的最长单词长度

最长单词:求能由其他单词拼接成的最长单词长度

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

哪些公司问过

小米1

常见岗位:C/C++ 软件开发

答案要点

  1. 把问题转化为单词拆分:判断一个词能否由集合中其他词拼接而成
  2. 按长度降序排序后逐个判断,第一个能拼成的词就是最长的,可以提前结束
  3. dp[i]表示前i个字符可拆分,转移为存在j使dp[j]为真且s[j..i)在集合中
  4. 判断时临时把当前词移出集合,保证它由其他词构成
  5. 每个词约O(L²)次子串查询,可用Trie加记忆化DFS优化查找

易错点

面试官常见追问

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

相关面试题