单词拆分:判断字符串能否由字典单词拼接
哪些公司问过
答案要点
- dp[i] 表示前 i 个字符能否拆分,dp[0]=true
- dp[i] 为真当且仅当存在 j 使 dp[j] 为真且 s[j..i) 在字典中
- 字典放入哈希集合加速查找,找到可行 j 即可跳出
- 按最长单词长度限制枚举范围,或用 Trie 从可达位置向后匹配
- 单词可重复使用,本质是完全背包式的可达性问题
易错点
- dp 数组下标与子串区间对应错误,出现差一错误
- 每次在列表里线性查找单词,没有用哈希集合
- 用贪心每次匹配最长或最短单词,无法回溯导致错误
面试官常见追问
- 如果要输出所有拆分方案(LC140)怎么做?
- BFS 能解吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场