交错字符串(LC97)
哪些公司问过
答案要点
- 先校验 len(s1) + len(s2) 是否等于 len(s3)
- dp[i][j]:s1 前 i 个与 s2 前 j 个能否组成 s3 前 i+j 个
- 转移:来自 dp[i-1][j] 且 s1 字符匹配,或 dp[i][j-1] 且 s2 字符匹配
- dp[0][0] 为真,首行首列单独初始化
- 时间 O(mn),滚动数组空间 O(n)
易错点
- 漏掉长度校验,导致越界或误判
- 下标偏移写错,s1 第 i 个字符应是 s1[i-1]
- 首行首列没有单独初始化
面试官常见追问
- 为什么双指针贪心不对?
- 记忆化 DFS 怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场