面试题库 › Java 后端 › 统计根到叶路径字符串为目标串子序列的路径数

统计根到叶路径字符串为目标串子序列的路径数

难度 ★★☆在 1 场真实面经中被问到 方向:Java 后端考点:树与二叉树

哪些公司问过

阿里巴巴1

答案要点

  1. 子序列只要求保持相对顺序、不要求连续,贪心匹配最早出现位置即可判定
  2. DFS 沿路径传递已匹配位置 j,回溯时自动恢复,无需拷贝路径串
  3. 预处理 next[i][c] 表,使每个节点的匹配推进为 O(1)
  4. 某节点匹配失败时整棵子树都可剪枝,只在叶子处计数
  5. 时间 O(n + m·Σ),并处理空树、单节点、多字符节点值等边界

易错点

面试官常见追问

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

相关面试题