面试题库 › Java 后端 › 交错字符串(LC97)

交错字符串(LC97)

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

哪些公司问过

腾讯1

常见岗位:Java 后端

答案要点

  1. 先校验 len(s1) + len(s2) 是否等于 len(s3)
  2. dp[i][j]:s1 前 i 个与 s2 前 j 个能否组成 s3 前 i+j 个
  3. 转移:来自 dp[i-1][j] 且 s1 字符匹配,或 dp[i][j-1] 且 s2 字符匹配
  4. dp[0][0] 为真,首行首列单独初始化
  5. 时间 O(mn),滚动数组空间 O(n)

易错点

面试官常见追问

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

相关面试题