单词搜索(LeetCode 79/212)DFS 回溯
哪些公司问过
答案要点
- 以每个格子为起点 DFS,逐字符匹配,四方向扩展
- 访问标记加回溯恢复:进入时标记,返回前恢复原值,防止同一格子重复使用
- 复杂度约 O(m·n·3^L),递归空间 O(L)
- 剪枝:字符频次不足直接返回,必要时反转单词从稀有字符一端开始
- 多单词版本(LC212)用 Trie 存字典,一次 DFS 同时匹配,并在找到后剪枝
易错点
- 忘记回溯恢复访问标记,导致其他路径无法使用该格子
- 越界判断放在访问数组之后,引发下标越界
- 多单词时对每个单词单独 DFS,复杂度过高
面试官常见追问
- LC212 用 Trie 怎么做?
- 为什么不用 visited 数组而是改原字符?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。