最长单词:求能由其他单词拼接成的最长单词长度
哪些公司问过
答案要点
- 把问题转化为单词拆分:判断一个词能否由集合中其他词拼接而成
- 按长度降序排序后逐个判断,第一个能拼成的词就是最长的,可以提前结束
- dp[i]表示前i个字符可拆分,转移为存在j使dp[j]为真且s[j..i)在集合中
- 判断时临时把当前词移出集合,保证它由其他词构成
- 每个词约O(L²)次子串查询,可用Trie加记忆化DFS优化查找
易错点
- 忘记排除单词自身,导致每个词都被判定为可以拼成
- 只检查能否由两个词拼成,漏掉三个及以上词拼接的情况
- 没先确认题意是「由其他词拼接」还是「逐个加字母构成」,两者解法不同
面试官常见追问
- 如果要返回所有能由其他词拼成的单词怎么做?
- 如果题意是每次加一个字母逐步构成(LeetCode 720)呢?
- 空字符串和重复单词怎么处理?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场