面试题库 › 算法 / 大模型 › 单词搜索(LeetCode 79/212)DFS 回溯

单词搜索(LeetCode 79/212)DFS 回溯

难度 ★★☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:贪心与回溯

哪些公司问过

小鹏1

常见岗位:机器学习算法(泛)、推理部署与加速

答案要点

  1. 以每个格子为起点 DFS,逐字符匹配,四方向扩展
  2. 访问标记加回溯恢复:进入时标记,返回前恢复原值,防止同一格子重复使用
  3. 复杂度约 O(m·n·3^L),递归空间 O(L)
  4. 剪枝:字符频次不足直接返回,必要时反转单词从稀有字符一端开始
  5. 多单词版本(LC212)用 Trie 存字典,一次 DFS 同时匹配,并在找到后剪枝

易错点

面试官常见追问

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

相关面试题