单词搜索:网格中是否存在单词(LC79)
哪些公司问过
答案要点
- 每个格子都作为起点做DFS
- 当前字符匹配后标记已访问,四个方向递归
- 回溯时恢复格子原值,保证其他路径可用
- 时间约O(M·N·3^L),空间为递归深度O(L)
- 可先做字符频次剪枝,或从首尾中更稀有的一端开始搜
易错点
- 回溯后没恢复格子,导致其他起点的搜索出错
- 在进入DFS前就标记,遗漏首字符匹配判断
- 匹配到最后一个字符后还继续扩展,越界判断顺序错误
面试官常见追问
- 如果要在网格里找一批单词(LC212)怎么办?
- 为什么不用BFS?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。